D - Summer Vacation

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : 400 points

Problem Statement

There are N one-off jobs available. If you take the i-th job and complete it, you will earn the reward of B_i after A_i 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 days from today.

You can already start working today.

Constraints

All values in input are integers.
1≤N≤10⁵
1≤M≤10⁵
1≤A_i≤10⁵
1≤B_i≤10⁴

Input

Input is given from Standard Input in the following format:

N  M

A₁ B₁

A₂ B₂

⋮⋮

A_N B_N

Output

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

Sample Input 1

Sample Output 1

You can earn the total reward of 5 by taking the jobs as follows:

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

题意

一共有N个任务和M天，一个人一天只能做一个任务，做完任务之后可以在第A_i天拿到B_i的工资，问M天内最多可以拿到多少工资

思路

贪心，按照领取工资间隔升序排序

设置一个优先队列用来储存当前可以做的任务并且可以在M天内拿到工资的任务的钱数，每次取可以拿到的最大值

代码

 1 #include <bits/stdc++.h>

 2 #define ll long long

 3 #define ull unsigned long long

 4 #define ms(a,b) memset(a,b,sizeof(a))

 5 const int inf=0x3f3f3f3f;

 6 const ll INF=0x3f3f3f3f3f3f3f3f;

 7 const int maxn=1e6+10;

 8 const int mod=1e9+7;

 9 const int maxm=1e3+10;

10 using namespace std;

11 struct wzy

12 {

13     int day,money;

14 }p[maxn];

15 bool cmp(wzy u,wzy v)

16 {

17     return u.day<v.day;

18 }

19 int main(int argc, char const *argv[])

20 {

21     ios::sync_with_stdio(false);

22     cin.tie(0);

23     int n,m;

24     cin>>n>>m;

25     for(int i=0;i<n;i++)

26         cin>>p[i].day>>p[i].money;

27     sort(p,p+n,cmp);

28     priority_queue<int>que;

29     int ans=0;

30     int pos=0;

31     for(int i=1;i<=m;i++)

32     {

33         while(p[pos].day<=i&&pos<n)

34             que.push(p[pos++].money);

35         if(!que.empty())

36             ans+=que.top(),que.pop();

37     }

38     cout<<ans<<endl;

39     return 0;

40 }

巴特西

Atcoder ABC137D：Summer Vacation（贪心）