智力大冲浪 Editional
E-智力大冲浪_Part1.1 基础算法-贪心算法
https://ac.nowcoder.com/acm/contest/950/E
因为题中的小游戏都是在1分钟完成的，所以我们并不需要考虑时间所带来的影响，和背包问题就有所不同，可以直接上贪心来做。
首先，先完成会罚款高的游戏明显明显更有益（时间消耗相同），所以，先要对游戏的罚款进行排序（从大到小）。
其次，排完序后，就要考虑这个游戏放在那个时间来做，很明显，我们要先处理罚款大的项，而又尽量不影响后面的游戏，只能将这个游戏放在规定最晚完成的时间段0-t的最后面t来做，若后面已经有游戏正在进行，可以考虑t-1，直到0，如果还没有对它进行安排，则这个游戏主动放弃0
最后，将放弃的游戏的罚款减去，即为所求解。
Code：
#include <bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for (int i=x;i<=y;i++)
struct Node{
int t,f;
}a[300000];// t代表最晚完成时间，f代表罚款。
bool f[100000]={0};//统计这个时间是否被游戏占领。
bool cmp(const Node &x,const Node &y)
{
return x.f>y.f;//返回罚款较大的。
}
int main()
{
int s,b,m,n,i,j;
cin>>m>>n;
s=0;
rep(i,1,n) cin>>a[i].t;
rep(i,1,n) cin>>a[i].f;
sort(a+1,a+1+n,cmp);//根据罚款进行从大到小排序。
rep(i,1,n)//从罚款最大的游戏进行处理。
{
for(j=a[i].t;j>=1;j--)//从最晚完成的时间判断，若被占领，则向前一步判断。
{
if(f[j]==0)//代表该时间无游戏占领。
{
f[j]=1;
a[i].f=0;//将占领的游戏的罚款变为零，因为按时完成了吗。
break;//重点，保证一个游戏只占领一个时间。占领后立刻结束循环。
}
}
}
rep(i,1,n) s=a[i].f+s;//统计罚款的总额
cout<<m-s<<endl;
return 0;
} 
拼多多集团-PDD公司氛围 517人发布
投递科大讯飞等公司10个岗位 >