programming.in.th · ข้อ 2031

จ้างคนงาน: งบเท่าเดิม ทีมใหญ่ได้แค่ไหน

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

★★★★☆ greedyheap อ่าน 12 นาที เผยแพร่ 11 กันยายน 2026 อัปเดต 20 ตุลาคม 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 งบ 40 ทั้งสามคนขอ 10 ดอลลาร์เท่ากัน คุณวุฒิ 1, 2, 3

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

คำตอบคือจำนวนคน (2) ไม่ใช่ยอดเงิน

ใบ้

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

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

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

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

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

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

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

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

เฉลย ตอนที่ 1 · ทีมหนึ่งทีมต้องจ่ายเท่าไร

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

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

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

ตัวเลขที่ต่ำที่สุดที่ใช้ได้คือ S/Q ที่สูงที่สุดในทีม ที่ตัวเลขนี้ อย่างน้อยหนึ่งคนได้เงินพอดีกับที่ขอ (คนที่ S/Q สูงสุด ถ้าเสมอกันหลายคนก็ได้พอดีทุกคนที่เสมอ) ที่เหลือได้เท่ากับหรือมากกว่าที่ขอ

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

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

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 ถ้าชวนคนที่ 1 เข้ามาด้วย อัตราจะกระโดดเป็น 10 รวม 60 เกินงบ

ทุกคนในตัวอย่างที่ 3 ขอ 10 ดอลลาร์ แต่คนที่คุณวุฒิสูงมีอัตราต่ำ เพราะเงินก้อนเท่ากันถูกหารด้วยคุณวุฒิที่มากกว่า

คนคุณวุฒิสูงถูกในแง่อัตรา แต่แพงในแง่ผลรวมคุณวุฒิ ทีมที่ดีต้องชั่งสองอย่างนี้

เฉลย ตอนที่ 2 · ทางแรกที่ถูกแต่ช้า

ทางแรกที่ผมเขียน

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

วิธีนี้ให้คำตอบถูก โค้ดที่ผมเขียนเรียงคุณวุฒิใหม่ทุกครั้งที่เปลี่ยนคนตั้งราคา วัดจริงที่ N = 5,000 ใช้ 0.68 ถึง 0.74 วินาที และที่ 20,000 ใช้ 14.2 วินาที

ถ้าเรียงคุณวุฒิครั้งเดียวตั้งแต่แรก แล้วแต่ละรอบเดินตามลำดับนั้นข้ามคนที่อัตราสูงเกิน ก็ตัด log ออกเหลือราว N²

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

สมมติว่าคนที่ j เป็นคนตั้งราคา เรียกคนที่อัตราไม่เกินเขาว่ากลุ่มที่ใช้ได้ ทีมรับได้เฉพาะคนในกลุ่มนี้

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

คำตอบคือจำนวนที่หยิบได้มากที่สุด เมื่อลองให้ทุกคนเป็นคนตั้งราคา ตารางนี้ทำแบบนั้นกับตัวอย่างที่ 1 งบ 100

ลองให้แต่ละคนเป็นคนตั้งราคา ตัวอย่างที่ 1
คนตั้งราคา	อัตรา	คุณวุฒิที่ใช้ได้ (น้อยไปมาก)	หยิบได้	ค่าจ้างรวม
คนที่ 1	0.005	1,000	1	5
คนที่ 2	0.1	100, 1,000	1	10
คนที่ 3	0.8	10, 100, 1,000	2	88
คนที่ 4	20	1, 10, 100, 1,000	1	20

แถวที่ได้มากที่สุดคือ 2 คน ตรงกับเอาต์พุต เรียงแถวตามอัตราแล้ว กลุ่มที่ใช้ได้ของแต่ละแถวคือกลุ่มของแถวก่อนบวกคนใหม่หนึ่งคน (เมื่ออัตราไม่ซ้ำกัน)

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

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

เฉลย ตอนที่ 3 · วิธีที่ทันทุกขนาด

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

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

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

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

มือ: คุณวุฒิของคนในทีมปัจจุบัน
sumQ: ผลรวมคุณวุฒิในมือ บวกตอนรับคนเข้า ลบตอนทิ้งคนออก
best: ขนาดมือที่ใหญ่ที่สุดที่เคยเห็น นี่คือคำตอบ

รอบของคนที่ j ทำสองขั้น

รับคุณวุฒิของเขาเข้ามือ บวก sumQ
ตราบที่ sumQ × S[j] > W × Q[j] (คือค่าจ้างรวมที่อัตราของเขาเกินงบ เขียนแบบคูณไขว้ให้เป็นจำนวนเต็ม) ทิ้งคนที่คุณวุฒิสูงสุดในมือออกหนึ่งคน

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

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

ที่เก็บที่หยิบ "ตัวที่คุณวุฒิสูงสุด" ออกได้เร็วซ้ำไปเรื่อย ๆ คือ ฮีป (heap) อ่านว่า "ฮีป" แปลตรงตัวว่ากองของ ในที่นี้คือกองตัวเลขที่จัดให้ตัวมากที่สุดอยู่บนสุดเสมอ

ตัวที่อยู่ข้างล่างเรียงกันแค่บางส่วน พอให้หาตัวบนสุดใหม่ได้เร็วหลังหยิบออก ใน C++ คือ priority_queue ใส่หนึ่งตัวหรือหยิบตัวบนสุดออก ใช้ราว log N ก้าว

log N (ล็อก N) คือจำนวนครั้งที่ต้องหาร N ครึ่งจนเหลือ 1 ที่ N = 500,000 คือราว 19 ทุกคนเข้าฮีปครั้งเดียวและออกได้ไม่เกินครั้งเดียว งานของฮีปทั้งหมดราว 2 × N × 19 ก้าว

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

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

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

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

ทีมแบบนี้ที่ดีที่สุดคือ c(j) คนที่คุณวุฒิน้อยที่สุดในบรรดาคนที่เดินผ่านมา

ผมจะแสดงว่าหลังจบรอบที่ j ในมือคือ c(j) คนนั้นพอดี คำตอบของโจทย์คือค่ามากที่สุดของ c(j) ตามตอนที่ 2

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

อัตราของรอบก่อนถูกกว่าหรือเท่ากัน ทีมที่เหลือนี้ก็จ่ายไหวที่อัตรานั้น รอบก่อนจึงได้อย่างน้อย c(j) - 1 คน

ข้อสอง ในมือหลังรับคนที่ j คือ c(j-1) คนที่คุณวุฒิน้อยที่สุดของรอบก่อน บวกเขาหนึ่งคน ถ้า c(j) ไม่เกิน c(j-1) ทุกคนที่รอบนี้ต้องใช้อยู่ในมือแล้ว

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

ที่เหลือของทีมคือ c(j-1) คนที่อยู่ในมืออยู่แล้ว

ทั้งสองกรณี c(j) คนที่ต้องการอยู่ในมือครบ การทิ้งตัวใหญ่สุดทีละคนจนงบพอ เหลือ c(j) คนนั้นพอดี

เทียบสามวิธี

โจทย์บน programming.in.th บอกแค่ขอบเขตเต็ม การ์ดกับตารางข้างล่างเลยเทียบกันตามขนาด N

วิธีที่ 1

ลองทุกทีม

ราว N × 2^N ก้าว

ทีมที่เป็นไปได้มี 2^N ทีม แต่ละทีมไล่ N คนหาคนตั้งราคากับผลรวมคุณวุฒิ ถูกแน่นอน ใช้เป็นตัวตรวจ

ทันถึงราว N = 24 · วัดได้ 0.07 วินาทีที่ N = 20

วิธีที่ 2

ตรึงคนตั้งราคาทีละคน

ราว N² + N² log N / 2 ก้าว

แต่ละคนกรองทั้งแถว N ก้าว แล้วเรียงกลุ่มที่ใช้ได้ ซึ่งเฉลี่ยราวครึ่งแถว

ทันถึงราว N = 8,200 · วัดได้ 0.68 ถึง 0.74 วินาทีที่ N = 5,000

วิธีเต็ม

เดินตามอัตรา พร้อมฮีป

ราว 3N log N ≈ 28 ล้านก้าว ที่ N = 500,000

เรียงครั้งเดียว N log N ทุกคนเข้าฮีปครั้งเดียว และออกไม่เกินครั้งเดียว ครั้งละ log N

ทันทุกขนาด · วัดได้ไม่เกิน 0.35 วินาทีที่ N = 500,000

จำนวนก้าวตามขนาด N
วิธี	N = 20	N = 5,000	N = 500,000
ลองทุกทีม	2.1 × 10⁷	7.1 × 10¹⁵⁰⁸	5 × 10¹⁵⁰⁵²⁰
ตรึงคนตั้งราคา	1,264	1.8 × 10⁸	2.6 × 10¹²
ท่าเต็ม	259	184,316	2.8 × 10⁷

เขียวคือไม่เกินงบ 5 × 10⁸ ก้าว (ลิมิต 2 วินาที คูณอัตราราว 2.5 × 10⁸ ก้าวต่อวินาทีที่วัดจากวิธีที่ 2) แดงคือเกิน log N ของแต่ละคอลัมน์คิดจาก N ของคอลัมน์นั้น

เดินตัวอย่างที่ 1 ทีละคน

ขั้น 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 ตรงกับเอาต์พุตของตัวอย่าง

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

โค้ด

ดูโค้ดเต็ม

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);
}

โค้ดส่วนไหนทำขั้นไหน
ส่วนในโค้ด	ของที่เก็บ	อธิบายไว้ที่
sort id ด้วยการคูณไขว้	id (ลำดับผู้สมัครตามอัตรา)	ตอนที่ 1 (อัตรา) และตอนที่ 3 (เดินจากถูกไปแพง)
heap.push, sumQ += Q[k]	heap (มือ), sumQ	ตอนที่ 3 รับคนเข้ามือ
ลูป while	heap, sumQ	ตอนที่ 3 ทิ้งคนคุณวุฒิสูงสุดจนงบพอ
best = max(...)	best	ตอนที่ 3 ขนาดมือที่ใหญ่ที่สุด

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

อัตราเทียบด้วยการคูณไขว้ ทุกการเทียบเป็นจำนวนเต็มล้วนและตรงเป๊ะ เลยตัดคำถามเรื่องการปัดเศษของ double ทิ้งไปได้ทั้งหมด

ดูโค้ดวิธีที่ 2 (ตรึงคนตั้งราคา)

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);
}

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

สองวิธีโลภที่ให้คำตอบผิด

ผู้สมัครในกล่องนี้เขียนเป็น (S, Q)

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

จ้างคนที่ขอเงินน้อยก่อน: เรียงตามเงินที่ขอจากน้อยไปมาก รับทีละคนถ้าทั้งทีมยังจ่ายไหว ไม่ไหวก็ข้ามคนนั้น (กรณีนี้ผมให้ทุกคนขอเงินไม่เท่ากัน)

ผู้สมัคร (1, 2) (3, 1) (4, 1) งบ 8 ได้ 1 คน คำตอบจริงคือ 2 คน วิธีนี้จ้าง (1, 2) ก่อนเพราะขอแค่ 1

พอจะรับ (3, 1) เพิ่ม อัตราทั้งทีมขึ้นเป็น 3 คนแรกซึ่งคุณวุฒิ 2 ต้องได้ 6 รวมทั้งทีม 9 เกินงบ ราคาจริงของเขาขึ้นกับคนตั้งราคา มากกว่าเงินที่เขาขอ

จ้างคนอัตราถูกที่สุด k คนแรกยกกลุ่ม: เรียงตามอัตรา แล้วหา k ที่มากที่สุดที่ k คนแรกจ่ายไหว ทีมต้องเป็น k คนแรกเสมอ ข้ามใครในนั้นไม่ได้

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

ตรวจอะไรไปแล้วบ้าง

ตัวอย่างในโจทย์: ทั้งสามโปรแกรมตอบ 2, 3, 2 ตรง
สุ่ม 2,000 เคส ผู้สมัครไม่เกิน 12 คน เทียบทั้งสามโปรแกรม: ตรงกันทุกเคส
สุ่ม 200 เคส ผู้สมัครไม่เกิน 300 คน เทียบโค้ดเต็มกับวิธีที่ 2: ตรงกันทุกเคส
ทุกครั้งที่สร้างหน้านี้ใหม่: เทียบวิธีที่ 2 และวิธีเต็มกับการลองทุกเซตย่อยอีก 500 เคส รวมทั้งทุกชุดในเกมและในกล่องวิธีโลภ
N = 500,000: 0.14 ถึง 0.17 ถึง 0.35 วินาที สูงสุดราว 17 MB (ลิมิต 2 วินาที 64 MB)

เวลาวัดบน WSL ด้วย g++ -O2 สามรอบ รวมเวลาอ่านอินพุต ทั้งหมดนี้ทดสอบแล้ว ไม่ได้พิสูจน์ และยังไม่ได้ส่งเกรดเดอร์จริง บทพิสูจน์ของวิธีเต็มอยู่ในตอนที่ 3

ทดสอบตัวเอง

ในตัวอย่างที่ 3 ทำไมจ้างครบสามคนไม่ได้ ทั้งที่ทุกคนขอ 10 เท่ากัน

คนคุณวุฒิ 1 มีอัตรา 10 สูงสุดในสามคน เขาเป็นคนตั้งราคา คุณวุฒิรวม 6 คูณ 10 ได้ 60 เกินงบ 40

ในตัวอย่างที่ 1 ทำไมคนคุณวุฒิ 1,000 ถูกทิ้งตอนคนที่ 2 เข้ามา

ในมือมีคุณวุฒิรวม 1,100 คูณอัตรา 0.1 ของคนที่ 2 ได้ 110 เกินงบ 100

ทิ้งตัวคุณวุฒิสูงสุดคือ 1,000 แล้วเหลือ 100 คูณอัตราได้ 10 อยู่ในงบ

ตอนงบเกิน ทำไมเลือกคนทิ้งตาม Q สูงสุด แทนที่จะทิ้งตามลำดับที่เข้ามา

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

ลำดับที่เข้ามาบอกแค่อัตรา ถ้าคนที่เพิ่งเข้ามาเป็นคนที่ Q สูงสุดพอดี ก็ทิ้งเขาตามกฎเดียวกันนี้

แหล่งที่มา

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