有N个任务,每个任务有一个最晚结束时间以及一个对应的奖励。在结束时间之前完成该任务,就可以获得对应的奖励。完成每一个任务所需的时间都是1个单位时间。有时候完成所有任务是不可能的,因为时间上可能会有冲突,这需要你来取舍。求能够获得的最高奖励。
Input
第1行:一个数N,表示任务的数量(2 <= N <= 50000)
第2 - N + 1行,每行2个数,中间用空格分隔,表示任务的最晚结束时间E
i
i以及对应的奖励W
i
i。(1 <= E
i
i <= 10^9,1 <= W
i
i <= 10^9)
Output
输出能够获得的最高奖励。
Sample Input
7
4 20
2 60
4 70
3 40
1 30
4 50
6 10
Sample Output
230
思路:先对分数进行排序,之后把所有的奖励全加在一起,之后模拟一遍,如果要求的天数还没达到最晚时间就往后排,实在是后面排不下了就总奖励减去这个奖励。
代码如下:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct node
{
long long x,y;
};
bool cmp(node n,node m)
{
if(n.y!=m.y)
return n.y>m.y;
else
return n.x<m.x;
}
int main()
{
int n,m,i,j;
struct node std[50010];
int a[50010];
scanf("%d",&n);
long long sum=0;
memset(a,0,sizeof(a));
for(i=0; i<n; i++)
{
scanf("%lld %lld",&std[i].x,&std[i].y);
sum+=std[i].y;
}
sort(std,std+n,cmp);
for(i=0; i<n; i++)
{
for(j=std[i].x; j>0; j--)//往尽可能的往后排
{
if(a[j]==0)
{
a[j]=1;
break;
}
}
if(j<=0)//后面的天数都已经排好了,又因为前面已经对分数排序了,所以只能减去这个奖励了
{
sum-=std[i].y;
}
}
printf("%lld\n",sum);
return 0;
}之后我用优先队列做了一遍对时间从小到大排序,之后进行模拟#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
struct node
{
int x,y;
};
bool cmp(node n,node m)
{
return n.x<m.x;
}
priority_queue<int,vector<int>,greater<int> >que;
int main()
{
int n,m;
struct node std[50001];
int i,j;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d %d",&std[i].x,&std[i].y);
}
long long ans=0;
sort(std,std+n,cmp);
for(i=0;i<n;i++)
{
int k=std[i].y;
if(std[i].x>que.size())
{
ans+=k;
que.push(k);
}
else
{
ans+=k;
que.push(k);
int min1=que.top();
ans-=min1;
que.pop();
}
}
printf("%lld\n",ans);
return 0;
}