AtCoder Beginner Contest 137 D - Summer Vacation——————贪心，优先队列

雨点打透心脏的1/2处 2021-11-01 08:14 282阅读 0赞

# [abc137\_D - Summer Vacation][abc137_D - Summer Vacation] #

**Problem Statement**  
There are  N N N one-off jobs available. If you take the i-th job and complete it, you will earn the reward of  B i B\_i Bi after  A i A\_i Ai days from the day you do it.  
You can take and complete at most one of these jobs in a day.  
However, you cannot retake a job that you have already done.  
Find the maximum total reward that you can earn no later than  M M M days from today.  
You can already start working today.

**Constraints**  
All values in input are integers.

*   1 ≤ N ≤ 1 0 5 1≤N≤10^5 1≤N≤105
 *   1 ≤ M ≤ 1 0 5 1≤M≤10^5 1≤M≤105
 *   1 ≤ A i ≤ 1 0 5 1≤A\_i≤10^5 1≤Ai≤105
 *   1 ≤ B i ≤ 1 0 4 1≤B\_i≤10^4 1≤Bi≤104

**Input**  
Input is given from Standard Input in the following format:

N N N  M M M  
 A 1 A\_1 A1  B 1 B\_1 B1  
 A 2 A\_2 A2  B 2 B\_2 B2  
 ⋮ ⋮ ⋮  
 A N A\_N AN  B N B\_N BN

Output  
Print the maximum total reward that you can earn no later than  M M M days from today.

Sample Input 1  
3 4  
4 3  
4 1  
2 2  
Sample Output 1  
5  
You can earn the total reward of  5 5 5 by taking the jobs as follows:

*  Take and complete the first job today. You will earn the reward of  3 3 3 after four days from today.
 *  Take and complete the third job tomorrow. You will earn the reward of  2 2 2 after two days from tomorrow, that is, after three days from today.

Sample Input 2  
5 3  
1 2  
1 3  
1 4  
2 1  
2 3  
Sample Output 2  
10  
Sample Input 3  
1 1  
2 1  
Sample Output 3  
0

--------------------

每天只能领取一个工作，不过每天可以做的工作可以有多个  
比如样例 1 1 1，第一天领取 4 3 4\\ 3 43，在第四天可以得到3的奖励，第二天领取 2 2 2\\ 2 22，第三天可以获得2的奖励

我们可以知道，在第 i i i天，不能领取工作时长超过 m − i + 1 m-i+1 m−i\+1的工作，于是我们就可以在这些满足条件的工作中选择奖励最高的。  
倒着想就行了，在倒数第 i i i天，我能选择的工作是：工作时长不超过 i i i的，在这些满足条件的工作中选择奖励最高的。  
用个优先队列维护一下，不过得先排序，按照天数递增排序

贪心，思维，优先队列

#include<bits/stdc++.h>
    using namespace std;
    const int MAXN = 1e5+7;
    typedef long long ll;
    
    struct node{
        
            ll a,b;
    }z[MAXN];
    
    bool cmp(node x,node y) {
        
            return x.a<y.a;
    }
    
    int main() {
        
            int n,m;
            while(cin>>n>>m) {
        
                    for(int i=0;i<n;++i)
                            cin>>z[i].a>>z[i].b;
                    sort(z,z+n,cmp);
                    ll ans = 0;
                    int id = 0;
                    priority_queue<ll> que;
                    for(int i=1;i<=m;++i) {
        
                            while(z[id].a<=i && id<n) {
        
                                    que.push(z[id].b);
                                    id++;
                            }
                            if(que.empty()) continue;
                            ans += que.top();
                            que.pop();
                    }
                    cout<<ans<<endl;
            }
            return 0;
    }

[abc137_D - Summer Vacation]: https://atcoder.jp/contests/abc137/tasks/abc137_d