programming.in.th · ข้อ 2031

จ้างคนงาน: คนเดียวในทีมเป็นคนตั้งราคาให้ทั้งทีม

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

★★★★☆ greedyheap อ่าน 12 นาที 11 กันยายน 2026

โจทย์ · จ้างคนงานให้ได้มากที่สุดภายใต้งบ

เรากำลังจะเปิดไซต์ก่อสร้าง มีผู้สมัคร N คน คนที่ k บอกมาสองอย่าง คือเงินเดือนขั้นต่ำที่เขายอมรับ S ดอลลาร์ และระดับคุณวุฒิ Q ใครที่เราจ้าง ต้องได้เงินไม่ต่ำกว่าที่เขาขอ

แต่มีกฎของสมาคมก่อสร้างมาขวางอยู่ข้อหนึ่ง คือค่าจ้างของคนที่เราจ้างต้องเป็นสัดส่วนกับคุณวุฒิพอดี ถ้าคนงาน A มีคุณวุฒิเป็นสามเท่าของคนงาน B เราต้องจ่าย A เป็นสามเท่าของที่จ่าย B เป๊ะ ๆ จะจ่ายเป็นเศษสตางค์ก็ได้ ไม่ต้องเป็นจำนวนเต็ม

เรามีงบ W ดอลลาร์ งานนี้ไม่สนเรื่องคุณวุฒิเลย ขอแค่จำนวนคนมากที่สุด ถามว่าจ้างได้มากที่สุดกี่คน

อินพุต / ขอบเขต / เอาต์พุต

อินพุต: บรรทัดแรกคือ N กับ W จากนั้นอีก N บรรทัด บรรทัดที่ k คือ S กับ Q ของผู้สมัครคนที่ k
ขอบเขต: 1 ≤ N ≤ 500,000, 1 ≤ S, Q ≤ 20,000, 1 ≤ W ≤ 10,000,000,000 (งบใหญ่เกิน 32 บิต ต้องใช้ long long) เวลา 2 วินาที หน่วยความจำ 64 เมกะไบต์
เอาต์พุต: จำนวนคนงานมากที่สุดที่จ้างได้ ตัวเลขเดียว

EXAMPLE
Input	Output
4 100 5 1000 10 100 8 10 20 1	2
3 4 1 2 1 3 1 3	3
3 40 10 1 10 2 10 3	2

ลองอ่านกฎการจ่ายเงินกับตัวอย่างที่ 3 ทั้งสามคนขอ 10 ดอลลาร์เท่ากัน ถ้าจ้างคนที่ 2 (คุณวุฒิ 2) กับคนที่ 3 (คุณวุฒิ 3) เราต้องจ่าย 10 กับ 15 ดอลลาร์ ทั้งคู่ได้ไม่ต่ำกว่าที่ขอ สัดส่วน 2 ต่อ 3 ถูกกฎ และรวมกัน 25 ไม่เกินงบ 40 คำตอบคือจำนวนคน ไม่ใช่ยอดเงิน

ใบ้

กฎสัดส่วนทำให้ทั้งทีมผูกกันด้วยตัวเลขตัวเดียว คือเงินที่จ่ายต่อหนึ่งหน่วยคุณวุฒิ พอตัวเลขนี้ถูกกำหนดแล้ว ค่าจ้างของทุกคนก็ตามมาเองหมด

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

ลองเอง · จัดทีมให้ใหญ่ที่สุดภายใต้งบ

สี่คนนี้มาจากตัวอย่างในโจทย์ ลองกดเลือกดู แล้วสังเกตว่าตัวเลขค่าจ้างของทุกคนเปลี่ยนตามใคร

ยังไม่ได้เลือกใคร

กดการ์ดเพื่อจ้างหรือปลดคนนั้น ตัวเลข "ได้" คือเงินที่เขาได้จริงตามกฎสัดส่วน

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

ลองจัดทีมให้ครบทั้งสี่ชุดก่อนนะครับ โดยเฉพาะชุดหกคนงบ 110 ที่คนขอเงินน้อยที่สุดกลับเป็นตัวถ่วง พอมีคำตอบในใจแล้ว ค่อยเปิดเฉลย

เฉลย ตอนที่ 1 · คนเดียวในทีมเป็นคนตั้งราคา

ที่มาของแนวคิดนี้

ผมเริ่มจากคำถามที่เล็กที่สุดก่อน คือถ้ามีทีมมาให้หนึ่งทีม จ่ายเท่าไร ยังไม่ถามเลยว่าทีมไหนดี เพราะถ้าคิดราคาของทีมเดียวยังไม่ออก ก็ยังไม่มีอะไรให้เพิ่มประสิทธิภาพ กฎสัดส่วนบอกว่าทุกคนได้ Q คูณตัวเลขตัวเดียวกัน พอเขียนเงื่อนไข "ได้ไม่ต่ำกว่าที่ขอ" ของแต่ละคนออกมา ก็เห็นว่าตัวเลขนั้นต้องไม่ต่ำกว่า S/Q ของทุกคนในทีม

ตรงนี้คือจุดที่โจทย์เปลี่ยนหน้าตา ตัวเลขที่ต่ำที่สุดที่ใช้ได้คือ S/Q ที่สูงที่สุดในทีม แปลว่าในทีมหนึ่งทีม มีแค่คนเดียวที่ได้เงินพอดีกับที่ขอ ที่เหลือได้เกินกันหมด และค่าจ้างรวมก็แยกเป็นผลคูณของสองก้อน คืออัตราของคนนั้นกับผลรวมคุณวุฒิของทั้งทีม สองก้อนนี้ยังผูกกันอยู่ แต่อย่างน้อยผมก็รู้แล้วว่ากำลังสู้กับอะไร

บทเรียนที่ยกไปข้ออื่นได้คือ ก่อนหาทีมที่ดีที่สุด ให้เขียนราคาของทีมเดียวออกมาเป็นสูตรก่อน สูตรนั้นมักบอกเองว่าต้องตรึงตัวไหนไว้

เรียก S/Q ของแต่ละคนว่าอัตราของเขา คือเงินขั้นต่ำที่เขาต้องการต่อหนึ่งหน่วยคุณวุฒิ ถ้าทีมจ่ายที่อัตรา r คนที่ k จะได้ r × Q ซึ่งไม่ต่ำกว่า S ก็ต่อเมื่อ r ไม่ต่ำกว่าอัตราของเขา ทีมจึงต้องจ่ายที่อัตราสูงสุดในทีม ค่าจ้างรวมคืออัตรานั้นคูณผลรวมคุณวุฒิของทั้งทีม

ราคาของทีมหนึ่งทีม

// ค่าจ้างรวมของทีม = (อัตราสูงสุดในทีม) x (ผลรวมคุณวุฒิของทีม)
// เทียบกับงบโดยไม่ต้องหาร:  sumQ * S[top] <= W * Q[top]
bool fits = sumQ * S[top] <= W * Q[top];

ตัวอย่างที่ 3 วางบนเส้นอัตรา ทีมของคนที่ 2 กับ 3 จ่ายที่อัตรา 5 ของคนขวาสุดในทีม รวม 25 ไม่เกินงบ 40 ถ้าชวนคนที่เหลือเข้ามาด้วย อัตราทั้งทีมจะกระโดดไปเป็น 10 และรวมเป็น 60 ซึ่งเกินงบ คนที่ขอเงินเท่ากันหมดจึงไม่ได้ราคาเท่ากันเลย

ภาพนี้อธิบายตัวอย่างที่ 3 ได้ทั้งข้อ ทุกคนขอ 10 ดอลลาร์ แต่คนที่คุณวุฒิสูงมีอัตราต่ำ เพราะเงินก้อนเท่ากันถูกหารด้วยคุณวุฒิที่มากกว่า การจ้างคนคุณวุฒิสูงจึงถูกในแง่อัตรา แต่แพงในแง่ผลรวมคุณวุฒิ โจทย์ทั้งข้อคือการชั่งสองแรงนี้

เฉลย ตอนที่ 2 · ตรึงคนตั้งราคา แล้วหยิบคุณวุฒิน้อยก่อน

ทางแรกที่ผมเขียน แล้วตีราคาทิ้ง

สูตรจากตอนที่ 1 มีสองก้อนผูกกัน ท่ามาตรฐานคือตรึงก้อนหนึ่งไว้ ผมตรึงอัตราก่อน เพราะอัตรามาจากคนคนเดียว จึงมีแค่ N ค่าให้ลอง ส่วนผลรวมคุณวุฒิมาจากทั้งทีม พอสมมติว่าคนที่ j เป็นคนตั้งราคา คนที่อัตราสูงกว่าเขาก็เข้าทีมไม่ได้ ส่วนคนที่อัตราไม่เกินเขา ใครเข้ามาก็จ่ายที่อัตราเดิม ราคาต่อหัวจึงขึ้นกับคุณวุฒิอย่างเดียว อยากได้คนเยอะก็หยิบคุณวุฒิน้อยก่อน จนงบหมด

ท่านี้ถูก และผมเขียนมันเป็นโค้ดจริงไว้ใช้เป็นตัวเทียบ แต่ต้องเรียงคุณวุฒิใหม่ทุกครั้งที่เปลี่ยนคนตั้งราคา ที่ N ห้าแสน คือราวสองแสนห้าหมื่นล้านครั้ง วัดจริงที่ N เท่ากับ 5,000 ใช้ไป 0.47 วินาทีแล้ว สิ่งที่ต้องหาต่อจึงชัดขึ้นมาก คือจะไม่ทิ้งงานที่ทำไปแล้วตอนเปลี่ยนคนตั้งราคาได้ยังไง

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

เฉลย ตอนที่ 3 · เดินจากอัตราถูกไปแพง แล้วทิ้งคนที่แพงที่สุดในมือ

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

สิ่งที่ถืออยู่ในมือคือคุณวุฒิของทีมปัจจุบัน รับคนที่ j เข้ามา แล้วถ้าผลรวมคุณวุฒิคูณอัตราของเขาเกินงบ ให้ทิ้งคนที่คุณวุฒิสูงสุดในมือออกทีละคนจนงบพอ เพราะที่อัตราเดียวกัน คนคุณวุฒิสูงคือคนที่แพงที่สุด จำนวนคนในมือหลังจบรอบคือทีมที่ใหญ่ที่สุดของคนตั้งราคาคนนี้ และคำตอบคือค่ามากที่สุดของตัวเลขนี้ตลอดทาง

แกะคำศัพท์ · heap

ของที่ต้องหยิบ "ตัวที่คุณวุฒิสูงสุด" ออกได้เร็ว ๆ ซ้ำไปเรื่อย ๆ คือฮีป (heap) คำนี้อ่านว่า "ฮีป" แปลตรงตัวว่ากองของ แบบกองผ้าที่ชิ้นบนสุดหยิบได้ทันที ส่วนชิ้นล่าง ๆ ไม่ได้เรียงกันเป๊ะ เพราะเราไม่เคยต้องใช้มัน ใน C++ คือ priority_queue ใส่ของหรือหยิบหัวกองออกครั้งละ log N

คำถามที่ควรค้างอยู่ในหัวตอนนี้คือ คนที่ถูกทิ้งไปแล้ว ไม่เคยถูกเรียกกลับเลย ถ้าอีกหลายรอบต่อมาเขากลับเป็นคนที่ควรอยู่ในทีมล่ะ คำตอบคือไม่มีทาง เขาถูกทิ้งตอนที่งบไม่พอแม้ที่อัตราถูกกว่า และอัตราหลังจากนี้มีแต่ขยับขึ้น ทีมที่ต้องมีเขาจึงมีแต่แพงขึ้นเรื่อย ๆ ขั้นตอนเต็มอยู่ในกล่องข้างล่าง

ทำไมคนที่ถูกทิ้งไม่ต้องเรียกกลับ

ให้ c(j) คือขนาดทีมที่ใหญ่ที่สุดเมื่อคนที่ j ตั้งราคา ผมจะแสดงว่าหลังจบรอบที่ j ในมือคือ c(j) คนที่คุณวุฒิน้อยที่สุด ในบรรดาคนที่เดินผ่านมาแล้ว ซึ่งเป็นทีมที่ตอนที่ 2 หยิบพอดี

ข้อแรก c(j) โตขึ้นจากรอบก่อนได้ไม่เกินหนึ่ง เอาทีมที่ดีที่สุดของรอบ j มา ตัดคนที่ j ออกถ้าเขาอยู่ในนั้น ที่เหลือเป็นคนจากรอบก่อนทั้งหมด และที่อัตราของรอบก่อนซึ่งไม่แพงกว่า ทีมนี้ก็จ่ายไหว รอบก่อนจึงได้อย่างน้อย c(j) - 1 คน

ข้อสอง ในมือหลังรับคนที่ j คือทีมเก่าบวกเขาหนึ่งคน ทีมเก่าเป็นคนคุณวุฒิน้อยที่สุดของรอบก่อน จึงครอบทุกคนที่ต้องใช้ในรอบนี้ไว้แล้ว ยกเว้นกรณีเดียวที่รอบนี้ใหญ่กว่ารอบก่อนหนึ่งคน ซึ่งข้อแรกบังคับว่าคนที่เพิ่มมาต้องเป็นคนที่ j เอง ที่เพิ่งรับเข้ามือพอดี การทิ้งตัวใหญ่สุดทีละคนจนงบพอ จึงเหลือ c(j) คนที่คุณวุฒิน้อยที่สุดตามต้องการ

ผมไม่ได้เชื่อบทพิสูจน์นี้อย่างเดียว ตัวตรวจที่ลองทุกเซตย่อยตรงกับท่านี้ทุกเคสที่สุ่ม และหน้าเว็บนี้ก็รันด่านตรวจเดียวกันตอนบิลด์ 500 ชุด

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

เดินฮีปให้ดูหนึ่งรอบ

ขั้น 0

เดินผู้สมัครของตัวอย่างที่ 1 จากอัตราถูกไปแพง งบ 100

ตัวอย่างที่ 1 เรียงตามอัตรา
คนที่	S	Q	อัตรา	คุณวุฒิในมือ	ทิ้ง	ค่าจ้างรวม	ในมือ
1	5	1,000	0.005	1,000	·	5	1
2	10	100	0.1	100	1,000	10	1
3	8	10	0.8	10, 100	·	88	2
4	20	1	20	1	100, 10	20	1

ขนาดในมือตลอดทางคือ 1, 1, 2, 1 ค่ามากที่สุดคือ 2 ตรงกับเอาต์พุตของตัวอย่าง สังเกตแถวสุดท้าย คนที่อัตราแพงที่สุดเข้ามาแล้วดันทุกคนออกจนเหลือตัวเขาคนเดียว แต่คำตอบไม่เสียหาย เพราะเราเก็บค่ามากที่สุดของทุกรอบไว้แล้ว

โค้ด

ดูโค้ดเต็ม

hiring.cpp

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    int n; ll W;
    if(scanf("%d %lld", &n, &W) != 2) return 0;
    vector<ll> S(n), Q(n);
    for(int i = 0; i < n; i++) scanf("%lld %lld", &S[i], &Q[i]);
    // เรียงตามอัตราค่าจ้างต่อหนึ่งหน่วยคุณวุฒิ S/Q จากน้อยไปมาก (เทียบด้วยการคูณไขว้ ไม่ต้องหาร)
    vector<int> id(n);
    iota(id.begin(), id.end(), 0);
    sort(id.begin(), id.end(), [&](int a, int b){ return S[a] * Q[b] < S[b] * Q[a]; });
    priority_queue<ll> heap;   // คุณวุฒิของคนที่ถืออยู่ ตัวใหญ่สุดอยู่บนหัว
    ll sumQ = 0;
    size_t best = 0;
    for(int k : id){
        heap.push(Q[k]); sumQ += Q[k];
        // อัตราตอนนี้คือ S[k]/Q[k] ค่าจ้างรวมคือ sumQ * S[k] / Q[k] ต้องไม่เกิน W
        while(!heap.empty() && sumQ * S[k] > W * Q[k]){
            sumQ -= heap.top(); heap.pop();   // ทิ้งคนที่คุณวุฒิสูงสุด เพราะเขาแพงสุดที่อัตรานี้
        }
        best = max(best, heap.size());
    }
    printf("%zu\n", best);
}

จุดที่ต้องระวังคือขนาดตัวเลข ผลรวมคุณวุฒิขึ้นได้ถึงหนึ่งหมื่นล้าน คูณ S อีกสองหมื่นเป็น 2 × 10¹⁴ ฝั่งงบก็ขนาดเดียวกัน ทุกตัวจึงเป็น long long และเทียบอัตราด้วยการคูณไขว้ เพื่อไม่ให้ทศนิยมของ double ทำให้อัตราที่เท่ากันพอดีเทียบผิด

ดูท่าตรึงคนตั้งราคา (ตัวเทียบระดับกลาง)

hiring_pivot.cpp

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    int n; ll W;
    if(scanf("%d %lld", &n, &W) != 2) return 0;
    vector<ll> S(n), Q(n);
    for(int i = 0; i < n; i++) scanf("%lld %lld", &S[i], &Q[i]);
    int best = 0;
    // ลองให้แต่ละคนเป็นคนที่อัตราสูงสุดในทีม
    for(int j = 0; j < n; j++){
        vector<ll> cand;   // คนที่อัตราไม่เกินคนที่ j
        for(int i = 0; i < n; i++)
            if(S[i] * Q[j] <= S[j] * Q[i]) cand.push_back(Q[i]);
        sort(cand.begin(), cand.end());
        ll sumQ = 0; int cnt = 0;
        for(ll q : cand){   // หยิบคุณวุฒิน้อยก่อน จนงบไม่พอ
            if((sumQ + q) * S[j] > W * Q[j]) break;
            sumQ += q; cnt++;
        }
        best = max(best, cnt);
    }
    printf("%d\n", best);
}

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

ดูตัวตรวจที่ใช้เทียบ

brute_hiring.cpp

// ตัวตรวจ ลองทุกเซตย่อยของผู้สมัคร ไม่มีการเรียงหรือฮีปใด ๆ
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    int n; ll W; scanf("%d %lld", &n, &W);
    vector<ll> S(n), Q(n);
    for(int i = 0; i < n; i++) scanf("%lld %lld", &S[i], &Q[i]);
    int best = 0;
    for(int m = 1; m < (1 << n); m++){
        // หาอัตราสูงสุดในเซต (เก็บเป็นเศษส่วน S/Q) แล้วคิดค่าจ้างรวม = อัตรา * ผลรวมคุณวุฒิ
        int top = -1; ll sumQ = 0;
        for(int i = 0; i < n; i++) if(m >> i & 1){
            sumQ += Q[i];
            if(top < 0 || S[i] * Q[top] > S[top] * Q[i]) top = i;
        }
        if(sumQ * S[top] <= W * Q[top]) best = max(best, __builtin_popcount(m));
    }
    printf("%d\n", best);
}

ตัวตรวจลองทุกเซตย่อย แล้วคิดราคาจากนิยามตรง ๆ ไม่ได้ใช้ข้ออ้างเรื่องเรียงอัตราหรือหยิบคุณวุฒิน้อยก่อนเลยสักข้อ ผมสุ่มผู้สมัครไม่เกิน 12 คน ค่าอยู่ในช่วงแคบบ้างกว้างบ้างเพื่อให้อัตราชนกันบ่อย รวม 800 เคส แล้วเทียบทั้งสามโปรแกรม ตรงกันหมด และตรงกับตัวอย่างทั้งสามในโจทย์

สองท่าที่ดูเข้าท่า แต่ผิด

จ้างคนที่ขอเงินน้อยก่อน ฟังดูประหยัด แต่เงินที่ขอไม่ได้บอกราคาต่อหน่วย ผู้สมัคร (1, 1) (1, 2) (1, 2) (เขียนเป็น (S, Q)) งบ 2 ท่านี้ได้ 1 คน ขณะที่คำตอบจริงคือ 2 คน คนที่ขอน้อยที่สุดมีอัตราสูง พอเขาเข้าทีมแล้ว ทุกคนที่ตามมาต้องได้ค่าจ้างที่อัตราของเขา

เรียงตามอัตราแล้วจ้างต่อกันไปโดยไม่ทิ้งใคร ใกล้เฉลยกว่า แต่พลาดตรงที่ไม่ยอมทิ้งคนคุณวุฒิสูงที่อัตราถูก ผู้สมัคร (1, 1) (2, 3) งบ 1 ท่านี้ได้ 0 คน ขณะที่คำตอบจริงคือ 1 คน

ทั้งสองกรณีเป็นกรณีที่เล็กที่สุดที่ท่านั้นพัง หน้าเว็บหาเองตอนบิลด์ ด้วยการไล่ทุกชุดผู้สมัครไม่เกินสามคน ที่ S กับ Q อยู่ระหว่าง 1 ถึง 4 แล้วเทียบกับการลองทุกเซตย่อย ชุดหกคนงบ 110 ในเกมข้างบนก็ทำให้ทั้งสองท่าแพ้ ด่านตรวจตอนบิลด์ยืนยันไว้แล้ว

เวลาที่วัดได้บนเครื่องผม ผู้สมัคร 500,000 คนที่ค่าสุ่มเต็มช่วง ใช้เวลา 0.32 วินาที ส่วนชุดที่งบน้อยจนฮีปต้องทิ้งคนแทบทุกรอบ ใช้ 0.29 วินาที จากลิมิต 2 วินาที ตัวเลขนี้รวมเวลาอ่านอินพุตหนึ่งล้านจำนวนด้วย

ท่าที่ติดมือกลับไป

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

บิลค่าใช้จ่าย
ทาง	ขอบเขตที่มันไหว	งานคร่าว ๆ
ลองทุกทีม	N ราว 20	2 ยกกำลัง N ทีม ที่ N เท่ากับ 500,000 เกินจะนับ
ตรึงคนตั้งราคาทีละคน แล้วเรียงคุณวุฒิใหม่ทุกครั้ง	N หลักพัน	ราว 500,000 ยกกำลังสอง คือสองแสนห้าหมื่นล้าน
เดินอัตราจากถูกไปแพงรอบเดียว พร้อมฮีป	N ถึง 500,000	ราว 9,500,000 ครั้ง (N คูณ log N)

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

สรุปบรรทัดเดียว

ทีมจ่ายที่อัตราของคนที่อัตราสูงสุดในทีม เดินคนตั้งราคาจากถูกไปแพง เก็บคุณวุฒิไว้ในฮีป งบเกินเมื่อไรก็ทิ้งคนคุณวุฒิสูงสุด แล้วตอบขนาดกองที่ใหญ่ที่สุดที่เคยเห็น

แหล่งที่มา

โจทย์ HIRING บน programming.in.th ข้อ 2031 programming.in.th/tasks/2031 (สืบค้น 11 กันยายน 2026)
ต้นฉบับคือโจทย์ Hiring วันแรกของ International Olympiad in Informatics ครั้งที่ 21 (IOI 2009, ประเทศบัลแกเรีย) ฉบับนั้นให้ตอบรายชื่อคนที่จ้างและถ้าจำนวนเท่ากันให้เลือกทีมที่จ่ายน้อยที่สุดด้วย ฉบับบน programming.in.th ตัดเหลือแค่จำนวนคน