# 【CSES】1630. Tasks and Deadlines

## [題目連結](https://cses.fi/problemset/task/1630/)

## **時間複雜度**

* $O(NlogN)$

## **解題想法**

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

### 貪心證明

這題的話，我們知道獎勵的算法是 $dead line - finishing$ $time$

首先可已發現，每題的 $\Sigma$ $d$ 都是一個固定值，所以如果我想要使 $d - f$ 有最小值的話，勢必是要盡可能的壓低 $\Sigma$ $f$ 的結果，這時候最好的做法就是去從小開始往大的貪心持續時間

### 補充

$\Sigma$ $d$ 跟 $\Sigma$ $f$ 的算法是一樣的，這邊以 $d$ 舉例：

$$
\left\{
\begin{aligned}
a_{1} = d_{1}\\
a_{n} = \sum_{i=1}^{n} d_{i}
\end{aligned}
\right.
$$

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

## **完整程式**

/* 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";
}