题解 P1230 【智力大冲浪】

· · 题解

这道题一看就是标准的贪心题。直接上思路。 思路：因为题中的小游戏都是在1分钟完成的，所以我们并不需要考虑时间所带来的影响，和背包问题就有所不同，可以直接上贪心来做。

第一点，先完成会罚款高的游戏明显明显更有益（时间消耗相同），所以，先要对游戏的罚款进行排序（从大到小）。

第二点，排完序后，就要考虑这个游戏放在那个时间来做，很明显，我们要先处理罚款大的项，而又尽量不影响后面的游戏，只能将这个游戏放在规定最晚完成的时间段0-t的最后面t来做，若后面已经有游戏正在进行，可以考虑t-1，直到0，如果还没有对它进行安排，则这个游戏主动放弃0

最后，将放弃的游戏的罚款减去，即为所求解。

附上代码

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct lao{
    int t,f;

}a[300000];// t代表最晚完成时间，f代表罚款。 
bool used[100000]={0};//统计这个时间是否被游戏占领。 
bool cmp(const lao &x,const lao &y)
{
    return x.f>y.f;//返回罚款较大的。 
}
int main()
{
    int s=0,b;
    int m,n,i,j;
    scanf("%d%d",&m,&n);
    for(i=1;i<=n;i++)
    scanf("%d",&a[i].t);
    for(i=1;i<=n;i++)
    scanf("%d",&a[i].f);
    sort(a+1,a+1+n,cmp);//根据罚款进行从大到小排序。 
    for(i=1;i<=n;i++)//从罚款最大的游戏进行处理。 
    {

        for(j=a[i].t;j>=1;j--)//从最晚完成的时间判断，若被占领，则向前一步判断。 
        {
            if(used[j]==0)//代表该时间无游戏占领。 
            {
                used[j]=1;
                a[i].f=0;//将占领的游戏的罚款变为零，因为按时完成了吗。 
                break;//重点，保证一个游戏只占领一个时间。占领后立刻结束循环。 
            }
        }



    }
    for(i=1;i<=n;i++)
    s=a[i].f+s;//统计罚款的总额 
    m=m-s;//m即为小伟最多能赢的钱。 
    printf("%d",m);

}