สำหรับข้อนี้ โดยเบื้องต้นแล้ว เราต้องรับค่ามาว่าหนังตอนที่ $i$ ต้องจ่ายราคาเท่าไหร่

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

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

ยกตัวอย่าง ถ้าค่าใช้จ่ายในการดูตอนที่ 1,2,3 เป็น 10,20,30 ตามลำดับ แทนที่จะเก็บเป็น [10,20,30] ก็ให้เก็บในรูปแบบ [10,30,60] แทน

โจทย์ต้องการให้ลูกค้าได้ดูจำนวนตอนมากที่สุดด้วยงบที่กำหนด ดังนั้นสิ่งที่เราต้องทำต่อคือการเรียงลำดับข้อมูลในอาเรย์ที่เก็บค่าจากการ Quick Sum (สำหรับโจทย์ข้อนี้ ค่าหลังการ Quick Sum ไม่ได้เรียงลำดับอัตโนมัติ เนื่องจากราคาติดลบได้)

หลังจากนั้นเราก็ต้องทำการตรวจสอบว่า ด้วยงบประมาณที่มี จะสามารถดูได้มากที่สุดกี่ตอน

ยกตัวอย่างเช่น สมมติให้ [30,10,50,40] เป็นข้อมูลที่ได้หลังการ Quick Sum ที่อธิบายว่าถ้าดูรวม 1 ตอนต้องใช้ 30 บาท แต่ถ้าดูรวม 2 ตอนจะใช้ 10 บาท เมื่อเรียงลำดับข้อมูลแล้ว (ได้เป็น [10,30,40,50]) จะเปลี่ยนการตีความเป็น "ถ้า 10 บาทดูได้ 2 ตอน 30 บาทก็ต้องดูได้ 2 ตอนเช่นกัน จะดูได้เพียงหนึ่งตอนไม่ได้" แทน

ส่วนสุดท้ายจะเป็นส่วนที่ให้งบประมาณของแต่ละคน แล้วโปรแกรมต้องตอบว่าดูได้มากที่สุดกี่ตอนเช่น [10,30,40,50] ถ้ามีงบ 35 บาทก็จะดูได้มากที่สุด 2 ตอน

ในส่วนนี้ มีสองทางเลือกในการค้นหาข้อมูล แบบแรกคือใช้ linear search แบบที่สองคือใช้ binary search (เร็วกว่าแน่นอน) ซึ่งจะเขียนด้วยตัวเองหรือจะใช้ lower_bound() ไม่ก็ upper_bound()ช่วยก็ได้

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

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

เช่นเก็บข้อมูลหลัง Quick Sum เป็น [<30,1>,<10,2>,<50,3>,<40,4>] แทน [30,10,50,40]

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

[<10,2>,<30,1>,<40,4>,<50,3>]

เราจะสามารถปรับเป็น

[<10,2>,<30,2>,<40,4>,<50,4>]

โดยไม่ต้องพึ่งอาเรย์เสริมที่อาจต้องสร้างเพิ่มได้ ช่วยลดความสับสนตอนเขียนลง

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

เช่นหลังจากที่เราเรียงข้อมูลแล้ว เราจะได้ <10,2> มาเป็นตัวแรกในลำดับ ซึ่งสามารถสื่อว่า ด้วยเงิน 10 บาทจะสามารถดูได้มากที่สุดทั้งหมด 2 ตอน และตัวต่อมาในลำดับจะเป็น <30,1> ที่สื่อว่า 30 บาทจะสามารถดูได้มากที่สุดทั้งหมด 1 ตอน

จากตรงนี้ จะเห็นได้ชัดเจนว่ามันผิดปกติที่เงินจำนวนมากกว่าจะดูจำนวนตอนได้น้อยกว่า ทำให้เรารู้ว่าจำเป็นต้องปรับว่า 30 บาทมันต้องดูจำนวนตอนได้ ไม่มากกว่าก็เท่ากับ จำนวนตอนที่เราดูได้ในราคา 10 บาท

ถึงเวลาคิดต่อว่า แล้ว 30 บาทควรดูได้มากที่สุดกี่ตอน ให้เราลองคิดว่า ก่อนเราปรับค่า เรามีเงิน 30 บาท เราดูได้แค่ 1 ตอน แต่ถ้ามีเงินแค่ 10 บาท เราดูได้ 2 ตอน แปลว่าถ้าเป็นแบบนั้นในชีวิตจริง เราก็คงเลือกถือเงินแค่ 10 บาทไปซื้อตอนสารคดี แล้วเราจะได้มา 2 ตอน แต่ยังไง เราก็มีเงิน 30 บาทไม่เปลี่ยนแปลง ดังนั้น 30 บาทก็ควรดูได้ 2 ตอนเช่นกัน เราจึงต้องปรับจาก <30,1> เป็น <30,2>

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

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

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

Solution Code in C++ Language

#include <bits/stdc++.h>
using namespace std;
int num[100010];
pair<int, int> adj[100010];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n, q;
  cin >> n >> q;

  for (int i = 1; i <= n; i++) {
    cin >> adj[i].first;
    adj[i].first += adj[i - 1].first;
    adj[i].second = i;
  }
  sort(adj + 1, adj + 1 + n);
  for (int i = 1; i <= n; i++) {
    num[i] = adj[i].first;
    adj[i].second = max(adj[i - 1].second, adj[i].second);
  }
  for (int i = 1; i <= q; i++) {
    int bud;
    cin >> bud;
    int upper = upper_bound(num + 1, num + 1 + n, bud) - (num + 1);
    cout << adj[upper].second << "\n";
  }
}

Time Complexity : $\mathcal{O}{(q\log n)}$