【CSES】1630. Tasks and Deadlines

題目連結

時間複雜度

• $O(NlogN)$

解題想法

這題的解法是去貪心持續時間，以下為貪心證明

貪心證明

這題的話，我們知道獎勵的算法是

$deadline-finishing$

$time$

首先可已發現，每題的

$\mathrm{\Sigma }$

$d$ 都是一個固定值，所以如果我想要使

$d-f$ 有最小值的話，勢必是要盡可能的壓低

$\mathrm{\Sigma }$

$f$ 的結果，這時候最好的做法就是去從小開始往大的貪心持續時間

補充

$\mathrm{\Sigma }$

$d$ 跟

$\mathrm{\Sigma }$

$f$ 的算法是一樣的，這邊以

$d$ 舉例：

$$\{\begin{array}{r}{a}_1=d_1\\ a_n=\sum _{i=1}^n{d}_i\end{array}$$

有了每一項之後就可以加總了，在數學上可能會麻煩一點，但是在程式中我只需要用一個變數去簡單紀錄就可以了

完整程式

/* Question : CSES 1630. Tasks and Deadlines */

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

#define opt ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define mem(x, value) memset(x, value, sizeof(x));
#define pii pair<int, int>
#define pdd pair<double, double>
#define f first
#define s second
#define int long long

const auto dir = vector< pair<int, int> > { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
const int MAXN = 1e8 + 50;
const int Mod = 1e9 + 7;
int n, a, b, ans, last, t;
vector<pii> w;

signed main(){
    opt;
    cin >> n;
    w.resize(n);
    for( int i = 0 ; i < n ; i++ ) cin >> w[i].f >> w[i].s;

    sort(w.begin(), w.end());

    t = 0;
    for( int i = 0 ; i < n ; i++ ){
        t += w[i].f;
        ans += w[i].s - t;
    }

    cout << ans << "\n";
}