programming.in.th · ข้อ 2015

ใบเรือโจรสลัด: แจกใบเรือลงระดับให้บังลมกันน้อยที่สุด

เสาสูงไม่เท่ากัน แต่ละต้นต้องติดใบตามจำนวน ใบที่อยู่ระดับเดียวกันบังลมกัน จะจัดยังไงให้เสียน้อยที่สุด ไล่จากวิธีนับทุกแบบไปจนถึงโค้ดที่ทันทุกขนาด

โจทย์ · ใบเรือที่บังลมกันเอง

เรือโจรสลัดลำใหม่มีเสา N ต้น เรียงจากหัวเรือไปท้ายเรือ เสาต้นที่ i สูง H ช่อง และต้องติดใบเรือ K ใบ หนึ่งช่องติดได้ไม่เกินหนึ่งใบ เราเลือกเองได้ว่าจะติดใบไหนที่ระดับไหนของเสาต้นนั้น

ใบเรือที่อยู่ข้างหน้าจะบังลมใบที่อยู่ข้างหลังในระดับเดียวกัน โจทย์นิยาม ความไร้ประสิทธิภาพ ของใบหนึ่งใบว่าคือจำนวนใบที่อยู่ข้างหน้ามันในระดับเดียวกัน คือจำนวนใบที่บังลมมัน

งานของเราคือจัดใบเรือให้ผลรวมความไร้ประสิทธิภาพของทุกใบน้อยที่สุด

สังเกตจุดหนึ่งที่ทำให้โจทย์ง่ายลงทันที ถ้าระดับหนึ่งมีใบเรืออยู่ c ใบ ผลรวมของระดับนั้นคือ จำนวนคู่ที่จับได้จาก c ใบ คือ c × (c − 1) / 2

สองใบในระดับเดียวกันย่อมมีใบหนึ่งอยู่หน้าอีกใบ จึงนับเป็นหนึ่งคู่พอดี ตัวเลขนี้ขึ้นกับจำนวนใบของระดับอย่างเดียว ลำดับหัวท้ายของเสาหายไปจากโจทย์

คำถามจึงเหลือแค่ แจกใบเรือลงระดับต่าง ๆ โดยเสาต้นที่ i แจกได้เฉพาะระดับ 1 ถึง H ระดับละไม่เกินหนึ่งใบ ทำยังไงให้ผลรวมของ c × (c − 1) / 2 ทุกระดับน้อยที่สุด

ลองเอง · วางใบเรือให้เสียแต้มน้อยที่สุด

ลองเทียบสองการจัดที่ต่างกันแค่ใบเดียว แล้วดูว่าแต้มเปลี่ยนไปเท่าไร

เฉลย · เริ่มจากกรณีที่ง่ายกว่า

long long v = at(H - K + 1);            // ค่าที่ระดับตัวที่ K นับจากท้ายช่วง [1..H]
// [l, r] = บล็อกของระดับที่มีค่าเท่ากับ v พอดี หาแบบไบนารีได้เพราะอาเรย์ไม่มีทางเพิ่มขึ้น
int below = H - r;                      // ระดับที่ค่าน้อยกว่า v อยู่ท้ายสุด ใส่ก่อนทั้งหมด
range(r + 1, H, 1);
int k2 = K - below;                     // ที่เหลือหยิบจาก "หัว" ของบล็อก ไม่ใช่ท้าย
if (k2 > 0) range(l, l + k2 - 1, 1);

ไล่ทีละเสาบนตัวอย่าง

อีกมุมหนึ่ง: ไล่ทุกวิธีจัด (ชุดทดสอบย่อย 25 คะแนน)

// เฉลยชุดทดสอบย่อย จำนวนวิธีจัดใบเรือทั้งหมดไม่เกินหนึ่งล้านแบบ (25 คะแนน)
// ไล่ทุกวิธีจัดจริง ๆ แล้วเก็บค่าที่น้อยที่สุด ไม่ต้องรู้อะไรเรื่องความโลภเลย
#include <bits/stdc++.h>
using namespace std;
int n, MX;
vector<int> H, K, cnt;
long long best = LLONG_MAX;

void rec(int i) {
    if (i == n) {
        long long v = 0;
        for (int c : cnt) v += 1LL * c * (c - 1) / 2;      // คู่ที่อยู่ระดับเดียวกัน
        best = min(best, v);
        return;
    }
    vector<int> pick(H[i], 0);
    fill(pick.begin(), pick.begin() + K[i], 1);
    sort(pick.begin(), pick.end());                        // เริ่มจากรูปแบบที่เล็กที่สุดของ next_permutation
    do {
        for (int h = 0; h < H[i]; h++) if (pick[h]) cnt[h]++;
        rec(i + 1);
        for (int h = 0; h < H[i]; h++) if (pick[h]) cnt[h]--;
    } while (next_permutation(pick.begin(), pick.end()));
}

int main() {
    scanf("%d", &n);
    H.resize(n); K.resize(n); MX = 0;
    for (int i = 0; i < n; i++) { scanf("%d %d", &H[i], &K[i]); MX = max(MX, H[i]); }
    cnt.assign(MX, 0);
    rec(0);
    printf("%lld\n", best);
}

โค้ด C++

#include <bits/stdc++.h>
using namespace std;
int MX; vector<long long> bit;                 // BIT แบบ range-update / point-query
void upd(int i,long long v){ for(;i<=MX;i+=i&-i) bit[i]+=v; }
void range(int l,int r,long long v){ if(l>r) return; upd(l,v); upd(r+1,-v); }
long long at(int i){ long long s=0; for(;i>0;i-=i&-i) s+=bit[i]; return s; }
int main(){
    int n; if(scanf("%d",&n)!=1) return 0;
    vector<pair<int,int>> m(n);
    for(auto&p:m) scanf("%d %d",&p.first,&p.second);
    sort(m.begin(),m.end());
    MX=m.back().first; bit.assign(MX+2,0);
    for(auto&[H,K]:m){
        long long v=at(H-K+1);
        // [l,r] = ช่วงใน [1..H] ที่ค่าเท่ากับ v พอดี (อาเรย์ไม่เพิ่ม จึงค้นแบบไบนารีได้)
        int l=1,r=H,lo,hi;
        lo=1; hi=H; int first=H+1;
        while(lo<=hi){ int md=(lo+hi)/2; if(at(md)<=v){ first=md; hi=md-1; } else lo=md+1; }
        l=first;
        lo=1; hi=H; int last=0;
        while(lo<=hi){ int md=(lo+hi)/2; if(at(md)>=v){ last=md; lo=md+1; } else hi=md-1; }
        r=last;
        int below=H-r;                 // ช่องที่ค่าน้อยกว่า v อยู่ท้ายสุด เติมก่อนทั้งหมด
        range(r+1,H,1);
        int k2=K-below;                // ที่เหลือหยิบจาก "หัว" ของบล็อกค่าเท่ากับ v
        if(k2>0) range(l,l+k2-1,1);
    }
    long long ans=0;
    for(int i=1;i<=MX;i++){ long long c=at(i); ans+=c*(c-1)/2; }
    printf("%lld\n",ans);
}

int below = H - r;                     // ระดับที่ค่าน้อยกว่า v อยู่ท้ายสุด ใส่ก่อนทั้งหมด
range(r + 1, H, 1);
int k2 = K - below;
if (k2 > 0) range(r - k2 + 1, r, 1);   // <-- บรรทัดที่ผิด หยิบจากท้ายบล็อก
                                       // ของจริงคือ range(l, l + k2 - 1, 1)

2
2 1
2 1

ข้อโต้แย้งแลกเปลี่ยน · รูปของคำตอบที่ดีที่สุด

ข้อโต้แย้งแลกเปลี่ยน (exchange argument) คือการดูคำตอบที่ดีที่สุดสักอัน แล้วลองย้ายการตัดสินใจหนึ่งครั้ง ถ้าการย้ายแบบหนึ่งลดแต้มได้เสมอ คำตอบที่ดีที่สุดย่อมไม่มีจุดแบบนั้น และเรารู้รูปของมันมากขึ้น

ใช้กับข้อนี้

ใบที่ c + 1 ของระดับหนึ่งจับคู่ใหม่กับ c ใบที่อยู่ก่อน แต้มจึงเพิ่ม c

ลองย้ายใบหนึ่งจากระดับ p ลงระดับ q ที่อยู่ต่ำกว่า แต้มลด cnt[p] − 1 (ใบนั้นเลิกจับคู่กับใบอื่นในระดับ p) และเพิ่ม cnt[q] (มันจับคู่ใหม่กับทุกใบในระดับ q)

แต้มสุทธิเปลี่ยน cnt[q] − (cnt[p] − 1) ค่านี้ติดลบเมื่อ cnt[q] ≤ cnt[p] − 2 และเพราะเป็นจำนวนเต็ม แต้มจึงลดอย่างน้อย 1 นี่คือเหตุที่ใช้ cnt[p] − 2 เป็นเงื่อนไข

• เสาที่มีใบที่ระดับ p มี cnt[p] ต้น ในนั้นมีใบที่ q ด้วยได้ไม่เกิน cnt[q] ต้น จึงมีอย่างน้อยหนึ่งต้นที่มีใบที่ p แต่ระดับ q ยังว่าง
• เสาต้นนั้นเอื้อมถึง q แน่ เพราะ q อยู่ต่ำกว่า p

คำตอบที่ดีที่สุดจึงมีระดับบนมากกว่าระดับล่างได้ไม่เกินหนึ่งใบ ท่าโลภสร้างรูปที่ผ่านเงื่อนไขนี้ เพราะระดับบนของมันไม่เคยมากกว่าระดับล่างเลย

เงื่อนไขนี้จำเป็น แต่ยังไม่พอบอกว่าท่าโลภได้ค่าที่น้อยที่สุดเสมอ ส่วนนั้นอาศัยการทดสอบในกรอบตรวจของหัวข้อโค้ด

เขียนอีกแบบ · คิวลำดับความสำคัญ

คิวลำดับความสำคัญ (priority queue) คือที่เก็บของที่หยิบตัวที่ค่าน้อยที่สุดออกได้ครั้งละราว log ก้าว

ท่าโลภเขียนตรง ๆ ได้ด้วยมัน เก็บคู่ (จำนวนใบ, ระดับ) ไว้ในคิว จำนวนใบน้อยขึ้นก่อน เท่ากันเอาระดับล่าง

• opened คือระดับสูงสุดที่ใส่ลงคิวแล้ว เสาที่สูงกว่านั้นเปิดระดับ opened + 1 ถึง H เพิ่มด้วยค่า 0
• แต่ละเสาหยิบออก k คู่ บวกจำนวนใบของระดับนั้น แล้วใส่กลับ
• ตอนเริ่มเสาแต่ละต้น ทุกระดับที่เปิดแล้วมีในคิวพอดีหนึ่งคู่ และค่าตรงกับ cnt
• จุดที่พลาดง่าย: หยิบครบ k ตัวก่อนแล้วค่อยใส่กลับ ถ้าใส่กลับทันที ระดับเดิมอาจยังมีใบน้อยที่สุด แล้วเสาต้นเดียวได้สองใบในระดับเดียว

โค้ดนี้ทำงานใบละครั้ง จึงช้าเมื่อใบรวมถึงหลายสิบล้าน (ตัวเลขอยู่ในการ์ดเทียบวิธี)

// ท่าโลภของโจทย์ใบเรือ เขียนด้วยคิวลำดับความสำคัญ
// ไล่เสาจากเตี้ยไปสูง แต่ละเสาหย่อนใบลงระดับที่ "ว่างที่สุด" ในระยะที่มันเอื้อมถึง
// อินพุต: n แล้ว n บรรทัด h k    เอาต์พุต: แต้มที่เสียน้อยที่สุด
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 0;
    vector<pair<int, int>> m(n);
    int H = 0;
    for (int i = 0; i < n; i++) { scanf("%d %d", &m[i].first, &m[i].second); H = max(H, m[i].first); }
    sort(m.begin(), m.end());                 // เตี้ยก่อน เพราะเสาเตี้ยมีตัวเลือกน้อยกว่า

    vector<int> cnt(H + 1, 0);                // cnt[l] = จำนวนใบที่ระดับ l (ระดับนับ 1..H)
    // คิวเก็บ (จำนวนใบตอนนี้, ระดับ) โดยเอาน้อยสุดขึ้นก่อน ค่าเท่ากันเอาระดับล่างก่อน
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    int opened = 0;                           // ระดับที่ปล่อยให้ใช้ได้แล้ว
    for (auto [h, k] : m) {
        while (opened < h) { ++opened; pq.push({cnt[opened], opened}); }
        // หยิบ k ระดับที่มีใบน้อยที่สุดออกมา ตอนเริ่มเสาแต่ละต้น ทุกระดับที่เปิดแล้วมีในคิวพอดีหนึ่งรายการ ค่าตรงกับ cnt
        vector<int> picked;
        picked.reserve(k);
        for (int t = 0; t < k; t++) {
            auto [c, lv] = pq.top();
            pq.pop();
            cnt[lv] = c + 1;
            picked.push_back(lv);
        }
        // ใส่กลับหลังหยิบครบ k ตัว ถ้าใส่กลับทันที เสาต้นเดียวอาจหยิบระดับเดิมซ้ำ
        for (int lv : picked) pq.push({cnt[lv], lv});
    }
    long long cost = 0;
    for (int l = 1; l <= H; l++) cost += (long long)cnt[l] * (cnt[l] - 1) / 2;
    printf("%lld\n", cost);
    return 0;
}

// ตัวตรวจอิสระของท่าโลภใบเรือ: ไล่ทุกวิธีจัดจริง
// ไม่รู้จักคำว่า "ว่างที่สุด" หรือลำดับเตี้ยไปสูงเลย จึงตรวจข้ออ้างของท่าโลภได้จริง
#include <bits/stdc++.h>
using namespace std;

int n, H;
vector<pair<int, int>> m;
vector<int> cnt;
long long best;

long long costNow() {
    long long c = 0;
    for (int l = 1; l <= H; l++) c += (long long)cnt[l] * (cnt[l] - 1) / 2;
    return c;
}

/** เลือก k ระดับจาก 1..h แบบไล่ทุกชุด */
void choose(int mast, int start, int left) {
    if (left == 0) {
        if (mast + 1 == n) best = min(best, costNow());
        else {
            int h = m[mast + 1].first, k = m[mast + 1].second;
            (void)h;
            choose(mast + 1, 1, k);
        }
        return;
    }
    int h = m[mast].first;
    for (int lv = start; lv <= h; lv++) {
        cnt[lv]++;
        choose(mast, lv + 1, left - 1);
        cnt[lv]--;
    }
}

int main() {
    if (scanf("%d", &n) != 1) return 0;
    m.resize(n);
    H = 0;
    for (int i = 0; i < n; i++) { scanf("%d %d", &m[i].first, &m[i].second); H = max(H, m[i].first); }
    cnt.assign(H + 1, 0);
    best = LLONG_MAX;
    choose(0, 1, m[0].second);
    printf("%lld\n", best);
    return 0;
}

ทดสอบตัวเองและสรุป

• แต้มของระดับที่มี c ใบคือ c × (c − 1) / 2
• ไล่เสาจากเตี้ยไปสูง ใส่ใบลงระดับที่มีใบน้อยที่สุด เสมอกันหยิบระดับล่าง
• ใบของแต่ละเสาลงไม่เกินสองช่วง เติมด้วย BIT

บทเรียนที่ยกไปใช้ได้: กฎตอนเสมอที่ไม่เปลี่ยนคำตอบ อาจยังเป็นสิ่งที่โค้ดชั้นในพึ่งพาอยู่

แหล่งที่มา

1. โจทย์ Sails บน programming.in.th ข้อ 2015 programming.in.th/tasks/2015 (สืบค้น 6 กันยายน 2026)
2. ต้นทางของโจทย์คือ 19th International Olympiad in Informatics ที่เมืองซาเกร็บ ประเทศโครเอเชีย วันแข่งที่ 1