โจทย์จาก TOI14 ข้อ NBK48 ใน programming.in.th

โจทย์

ความยาก ★★★☆☆

มีสารคดีทั้งหมด $N$ ตอน แต่ละเรื่องมีค่ารับชม $p_i$ บาท ในการรับชมสารคดี เราจะต้องดูต่อเนื่องกันตั้งแต่ตอนที่ $1$ ถึงตอนที่ $a$ โดยที่สามารถเลือกค่า $a$ เองได้ โดยจะต้องเสียค่ารับชม $p_1,p_2,p_3,...,p_a$ บาท

โดยโจทย์จะมีคำถามทั้งหมด $Q$ คำถาม ในแต่ละครั้งจะถามว่าถ้ามีเงิน $q_j$ บาทจะสามารถชมสารคดีได้ทั้งหมดมากที่สุดกี่ตอน

โจทย์เต็มข้อ NBK48

https://programming.in.th/tasks/toi14_nbk48

ข้อมูลนำเข้า

บรรทัดแรก : บรรทัดแรก ระบุจำนวนเต็ม $N,Q$ ( $1\leq N,Q \leq 100000$ ) แทนจำนวนสารคดี และคำถาม

บรรทัดต่อมา ระบุจำนวนเต็ม $p_i$ ทั้งหมด $N$ ตัว แทนค่ารับชมของตอนที่ $i$ ( $-10,000\leq p_i\leq 10,000$ )

Q บรรทัดต่อมา ระบุจำนวนเต็ม $q_j$ แทนจำนวนเงินของการถามครั้งที่ $j$ ( $0\leq q_j\leq 1,000,000,000$ )

ข้อมูลส่งออก

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

ตัวอย่าง

Input	Output
5 1 10 20 -10 30 60 25	3

มีสารคดีทั้งหมด 5 ตอน

ตอนที่ 1 เสีย 10
ตอนที่ 2 เสีย 20
ตอนที่ 3 เสีย -10
ตอนที่ 4 เสีย 30
ตอนที่ 5 เสีย 60

ถ้ามีเงินทั้งหมด 25 บาทจะดูได้ถึงตอนที่ 3 เพราะจะใช้เงินเพียง 10 + 20 - 10 = 20 บาท

คำใบ้

ลองคิดกรณีที่ทุกตอนมีค่าไม่ติดลบก่อนแล้วค่อยๆ เริ่มคิดกรณีมีค่าติดลบ

วิเคราะห์โจทย์

ตอนแรกเราจะมาคิดกันก่อนว่าการที่จะดู $a$ ตอนแรก จะคำนวณค่ากันยังไง

เรารู้อยู่แล้วว่าถ้าดูแค่ตอนแรก ก็จ่ายแค่ตอนแรก ดังนั้นถ้าเรามี array ที่ใช้เก็บค่าใช้จ่ายในการดู ตั้งแต่ตอนแรกถึงแต่ละตอน (เรียกว่า cost ละกัน)

cost[1] ก็จะเท่ากับ $p_1$ เลย

ทีนี้จะคำนวณค่าดูถึงตอนที่ 2 จะต้องใช้ค่าดูตอนแรกรวมกับค่าดูตอนที่ 2 ซึ่ง สามารถเขียนได้ว่า

cost[2] = cost[1] + p_2

และถ้าสังเกตตอนถัดๆไป ค่าดูจากตอนแรกไปถึงตอนที่ i ก็จะเขียนได้ว่า

cost[i] = cost[i-1] + p_i

สมมติตารางค่าดูแต่ละตอนเป็นดังนี้

array cost ค่าดูแต่ละตอนแยกกัน

ดังนั้นจากค่าดูแต่ละตอน เราก็สามารถแปลงเป็นค่าดูตั้งแต่ตอนแรกถึงตอนที่ $i$ ได้

array cost เมื่อคำนวณค่าดูตั้งแต่ตอนแรกแล้ว

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

อย่างเช่นว่าถ้าเรามีเงิน 11 บาท ก็จะได้ว่า:

ตอนที่ 4 ใช้เงิน 7 บาท ลองไปเช็กตอนถัดไปได้

ถ้าดูถึงตอนที่ 4 จะใช้เงิน 7 บาท ซึ่งเรามีเงินพอดูถึงตอนนี้ได้ (11)

ตอนที่ 6 ใช้เงิน 13 บาท มีเงินไม่พอแล้ว ต้องดูถึงแค่ตอนก่อนหน้า

ถ้าไปดูถึงตอนที่ 6 เลย จะต้องใช้เงิน 13 ซึ่งมีไม่พอ ดังนั้นก็ไม่สามารถดูตอนหลังจาก 6 ได้เหมือนกัน

ตอนที่ 5 ใช้เงิน 9 บาท มีเงินพอ และเพราะตอนที่ 6 ดูไม่ได้ ก็ตอบ 5

เราก็จะเหลือว่าต้องตรวจสอบว่าดูถึงตอนที่ 5 ได้ไหม

แล้วถ้าค่ารับชมเป็นลบล่ะ?

เราจะไม่สามารถใช้วิธี binary search ในการหาคำตอบได้แล้ว เพราะว่า array cost มันไม่ได้เรียงกันเหมือนเดิม

บางทีดูถึงตอนที่ 2 ต้องจ่าย 6 บาท แต่ถ้าดูถึงตอนที่ 5 อาจจะไม่ต้องจ่ายเลยก็ได้

-4

-6

-1

array cost ค่าดูแต่ละตอนแยกกัน แต่ติดลบ

-1

array cost อันใหม่ คำนวณค่าดูตั้งแต่ตอนแรกโดยที่มีตอนติดลบ

คำถามที่น่าคิดคือ…

ถ้าดูถึงตอนที่ i มันต้องจ่ายแพงกว่าดูเพิ่มไปอีกตอน แล้วเราสมควรดูเพิ่มไหม?

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

-1

ถ้าดูถึงตอนที่ 5 จะจ่ายน้อยกว่าถึงแค่ตอนที่ 4

อย่างในตัวอย่างล่าสุด ถ้าการดูถึงตอนที่ 5 จะต้องจ่าย 0 บาท แต่ถ้าดูไม่ถึงจะต้องจ่ายมากกว่า 0 บาท ทำไมถึงจะหยุดก่อนตอนที่ 5 ล่ะ?

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