แนวคิด

โจทย์ข้อนี้เป็นแนว Greedy Algorithm

เราจะนิยามตัวแปร $C_{i}$ เป็นคะแนนที่ได้จากการทำภารกิจที่ $i$ ดังนั้น $C_{i} = B_{i} - 2 * A_{i}$ (โจทย์ได้กำหนดไว้)

หลังจากที่เราได้ค่า $C_{i}$ ตั้งแต่ภารกิจที่ $1$ ถึง $N$ แล้วเราจะทำการ Sort ค่า $C_{i}$ ทั้งหมดจากมากไปน้อย โดยจะสมมติว่าได้เป็น $C'_{i}$ ออกมาแล้วจะพิจารณาคะแนนรวมที่มากที่สุดหลังหักค่าปรับแล้วจาก $(\sum_{j=1}^{i} C'_{j}) - (N - i)^{2}$ โดยที่ $i = 1 ... n$

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

ทำไมถึงสามารถใช้วิธีนี้ได้

จุดสังเกตคือ ถ้าจำนวนภารกิจที่เราไม่ได้ทำนั้นเท่ากัน การเลือกภารกิจที่จะทำนั้นไม่ได้ส่งผลต่อการเปลี่ยนแปลงของค่าปรับ หมายความว่าถ้าเราทำเลือกภารกิจจำนวน $P$ ภารกิจเราจะต้องเสียค่าปรับเท่ากับ $(N - P)^{2}$ เสมอ

ดังนั้นหากต้องการเลือกภารกิจ P อย่าง เราควรจะเลือกภารกิจที่ได้คะแนนมากสุด P ภารกิจก่อนเสมอ

ซึ่งถ้าเรา Sort $C_{i}$ จากมากไปน้อยแล้วเลือกตั้งแต่ตัวที่ $1$ ถึงตัวที่ $P$ จะการันตีว่าเราจะได้ผลรวมของคะแนนที่มากที่สุดก่อนหักค่าปรับจากการทำภารกิจ $P$ ภารกิจ

โค้ดตัวอย่างในภาษา C++

#include <bits/stdc++.h>

using namespace std;

vector<long long> c;

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    long long a, b;
    scanf("%lld %lld", &a, &b);
    c.push_back(b - 2 * a);
  }
  sort(c.begin(), c.end(), greater<long long>());
  long long ans = -((long long)n * (long long)n), notdo = n, now_sum = 0;
  for (auto i : c) {
    now_sum += i;
    notdo--;
    ans = max(ans, now_sum - (notdo * notdo));
  }
  printf("%lld", ans);
}