Description

Farmer John 有太多的工作要做！为了让农场高效运转，他必须靠他的工作赚钱，每项工作花一个单位时间。

他的工作日从0时刻开始，有 10^9109 个单位时间。在任一时刻，他都可以选择编号 1~N1 N 的 NN (1 \le N \le 10^5)(1≤N≤105) 项工作中的任意一项工作来完成。 因为他在每个单位时间里只能做一个工作，而每项工作又有一个截止日期，所以他很难有时间完成所有 NN 个工作，虽然还是有可能。 对于第 ii 个工作，有一个截止时间D_iDi (1 \le D_i \le 10^9)(1≤Di≤109)，如果他可以完成这个工作，那么他可以获利P_iPi (1 \le P_i \le 10^9 )(1≤Pi≤109)。

在给定的工作利润和截止时间下，FJ能够获得的利润最大为多少呢？

Input

• 第1行：一个整数N. 第2~N+1行：第i+1i+1行有两个用空格分开的整数：D_iDi和P_iPi.

Output

• 输出一行，里面有一个整数，表示最大获利值。

Sample Input 1

3
2 10
1 5
1 7

Sample Output 1

17

Hint

第1个单位时间完成第33个工作(1,7)(1,7)，然后在第22个单位时间完成第11个工作(2,10)(2,10)以达到最大利润

大多数情况下贪心算法失败的原因是->鼠目寸光

然后这个题用了"带反悔的贪心"

这个地方我觉得我理解得还不够好,我准备先去康康<算法导论>是怎么讲的,然后再回来装逼

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
#include<utility>

using namespace std;

const int MAX_N = 1e5 + 7;

typedef pair<int, int> P;//代表work,first代表价值, second代表ddl

typedef struct _Work{
    int val , ddl;
}Work;

priority_queue<P, vector<P>,greater<P> > que;//每次取最小的
Work work[MAX_N];
int N;


bool cmp(Work a,Work b){
    if(a.ddl!=b.ddl) return a.ddl < b.ddl;
    return a.val > b.val;
}

int main(){
    ios::sync_with_stdio(0);
    cin >> N;
    for (int i = 1; i <= N; i++){
        cin >> work[i].ddl >> work[i].val;
    }   
    long long ans = 0;
    sort(work + 1, work + N + 1, cmp);
    for (int i = 1; i <= N; i++){
        int ddl = work[i].ddl;
        int v = work[i].val;
        if(ddl<=que.size()){
            P p = que.top();
            if(p.first<v){//反悔
                ans -= p.first;
                ans += v;
                que.pop();
                que.push(P(work[i].val, work[i].ddl));
            }
        }else{
            ans += v;
            que.push(P(work[i].val,work[i].ddl));
        }
    }
    cout << ans << endl;
    return 0;
}