ข้อสอบท้ายค่าย 2 ปีการศึกษา 2566 ศูนย์ สอวน. มหาวิทยาลัยเทคโนโลยีพระจอมเกล้าธนบุรี ข้อ Heroes

---

Author: Nagorn Phongphasura

---

Problem

สรุปโจทย์

มีฮีโร่ \(N\) คน คนที่ \(i\) มีพลัง \(H_i\) โดยแต่ละคนจะอยู่ในคนละเซิร์ฟเวอร์ ในแต่ละเซิร์ฟเวอร์จะมีมอนสเตอร์ตัวเดียวกันทั้งหมด โดยจะมีมอนสเตอร์ \(M\) ตัว ตัวที่ \(i\) มีพลัง \(P_i\) ถ้าสู้ชนะจะได้เหรียญ \(C_i\) การที่ฮีโร่คนที่ \(i\) จะชนะมอนสเตอร์ตัวที่ \(j\) ได้นั้น จะต้องมี \(H_i \ge P_j\)

สิ่งที่ต้องทำ

หาจำนวนเหรียญที่มากที่สุดที่ฮีโร่แต่ละคนสามารถได้จากการสู้กับมอนสเตอร์

Constraints

\(1 \leq N \leq 2 \cdot 10^5\)
\(1 \leq M \leq 8 \cdot 10^5\)
\(1 \leq H_i \leq 10^9\)
\(1 \leq P_i \leq 10^9\)
\(0 \leq C_i \leq 10^9\)

Prerequisites

• Prefix Sum
• Binary Search

---

Solution

วิธีทำ

สังเกตว่า ฮีโร่ที่มีพลัง \(H_i\) จะสามารถเก็บเหรียญจากมอนสเตอร์ทุกตัวที่มีพลัง \(\leq H_i\) ได้เสมอ ดังนั้น สิ่งที่เราต้องทำ คือ เรียงลำดับมอนสเตอร์จากพลังน้อยไปมาก แล้วในการหาคำตอบของฮีโร่คนที่ \(i\) เราก็แค่ต้องหาผลรวมของ \(C_i\) ของมอนสเตอร์ทุกตัวที่มีพลัง \(\leq H_i\)

ดังนั้น ตอนนี้ สิ่งที่เราต้องการ คือวิธีการหาผลรวมของเหรียญของมอนสเตอร์ที่มีพลังน้อยที่สุด จนถึงมอนสเตอร์ที่มีพลังมากที่สุดที่ \(\leq H_i\)

แนวคิด

สังเกตอีกครั้งว่า ถ้าเราเรียงมอนสเตอร์โดยเรียงจากค่าพลัง และเราสามารถหา index ของมอนสเตอร์ที่มีพลังมากที่สุดที่ \(\leq H_i\) แล้ว เราแค่ต้องหาวิธีการหาผลรวมตั้งแต่มอนสเตอร์ตัวที่พลังน้อยสุด จนถึงมอนสเตอร์ตัวดังกล่าว

ซึ่งจากที่กล่าวมา เครื่องมือที่หาผลรวมของข้อมูลได้ในเวลาสั้นๆ ก็คงหนีไม่พ้น Prefix Sum นั่นเอง

หลังจากเราเรียงข้อมูลแล้ว เราแค่ต้องเก็บ Prefix Sum จากมอนสเตอร์ตัวแรก ถึงมอนสเตอร์ตัวสุดท้าย

และเราก็สามารถหา index ของมอนสเตอร์ตัวที่มีค่าพลังมากที่สุดที่ \(\leq H_i\) ได้โดยการใช้ Binary Search ซึ่งเนื่องจากเป็นการ Binary Search ตรงๆ ในกรณีนี้ เราก็สามารถใช้ upper_bound() ในการหาตรงๆได้เลย

ดังนั้น สำหรับฮีโร่แต่ละคน จำนวนเหรียญที่มากที่สุดที่สามารถได้จากการตีมอนสเตอร์ คือ \({pref}_{index}\) นั่นเองครับ

---

Code:

c2_kmutt_66_heroes.cpp

#include <bits/stdc++.h>
#define int long long
using namespace std;

int32_t main() {
    cin.tie(NULL)->sync_with_stdio(false);

    // input
    int n, m;
    cin >> n >> m;
    vector <int> a(n), ans(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector <pair <int, int>> mon(m);
    for (int i = 0; i < m; i++) {
        cin >> mon[i].first >> mon[i].second; // P[i], C[i]
    }

    sort(mon.begin(), mon.end()); // เรียงช้อมูลตามค่า P

    vector <int> power(m);
    for (int i = 0; i < m; i++) {
        power[i] = mon[i].first; // ดึงค่า P มาเก็บใน Array ใหม่
    }

    // Prefix Sum ของ C[i]
    vector <int> pref(m);
    pref[0] = mon[0].second;
    for (int i = 1; i < m; i++) {
        pref[i] = pref[i - 1] + mon[i].second;
    }

    // หาคำตอบของฮีโร่แต่ละคนโดยการใช้ Binary Search
    for (int i = 0; i < n; i++) {
        int idx = upper_bound(power.begin(), power.end(), a[i]) - power.begin() - 1; // หา index (ในที่นี้ ตั้งชื่อว่า idx)
        if (idx < 0) continue; // idx < 0 นั่นคือ ฮีโร่คนที่ i ไม่สามารถชนะมอนสเตอร์ตัวไหนได้เลย
        ans[i] = pref[idx]; // คำตอบของฮีโร่คนที่ i คือ pref[idx]
    }

    // Output
    for (int i = 0; i < n; i++) {
        cout << ans[i] << "\n";
    }

    return 0;
}

Total Time Complexity

\(O((m + n) \log m)\)

• \(m \log m\) มาจากการเรียงพลังและเหรียญของมอนสเตอร์
• \(n \log m\) มาจากการคำนวณจำนวนเหรียญที่มากที่สุดที่ฮีโร่แต่ละคนสามารถได้จากการตีมอนสเตอร์ตอนท้าย