智力大冲浪 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;
}


全部评论

相关推荐

2 收藏 评论
分享
牛客网
牛客企业服务