题解 P1230 【智力大冲浪】

· · 题解

前言：

一年不来发现点赞已经那么多了，占了一楼，而题解却是无脑搬运，想整改一下，争取给大家最新的阅读体验，如果本题解对你有帮助就请不吝赐赞。

题目链接:

https://www.luogu.org/problem/P1230

分析：

这道题我们每完不成一个任务就要扣钱，而想让自己最后的钱最多，就是扣的钱最少，而我们可以贪心的让能扣钱最多的排在最前面考虑，因为它的影响最大。

这时候用sort就行

sort(a+1,a+n+1,cmp)

为什么要用cmp？因为包含了结构体

struct ben
{
    int t,val;
}a[505];

注意此时cmp需要手写

int cmp(const ben &a,const ben &b)
{
    return a.val>b.val;
}

注意其中>与<的区别

然后我们直觉的思路就是设一个时间记录器来每次++判断。

但这是一个错误的贪心，按照样例来算答案会是9900

因为我们在保证花费降序时对时间要求完全是一个杂乱无章的处理。

可能值钱的任务时间限制也宽，有些即使不值钱的任务也容易超时，然而此时却完全可以避免那个即使便宜的任务的损耗。

我们考虑最优贪心，就是每一个任务都在最后一秒做，因为时间\leq500,可以设一个vis数组记录此时间是否被占用，当然，如果最后一秒被占用，就依次往前推，直到找到

在越往后做，才能给其他时间紧的任务腾出时间，而又优先考虑大任务的完成，如果本任务已经没时间了就真的只能掏钱了。。。

code:

#include<cstdio>
#include<algorithm>
using namespace std;
struct ben
{
    int t,val;
}a[505];
int vis[505];
int cmp(const ben &a,const ben &b)
{
    return a.val>b.val;
}
int main()
{
    int m,n;
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i].t);
    } 
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i].val);
    } 
    sort(a+1,a+n+1,cmp);
    int ans=0,t=0;
    for(int i=1;i<=n;i++)
    {
        int tag=0;
        for(int j=a[i].t;j;j--)
        {
            if(vis[j]==0)
            {
                vis[j]=1;
                tag=1;
                break;
            }
        }
        if(tag==0)
        {
            for(int j=n;j;j--)
            {
                if(vis[j]==0)
                {
                    vis[j]=1;
                    break;
                }
            }
            ans+=a[i].val;
        }
    }
    printf("%d\n",m-ans);
    return 0;
}

以下为旧版题解，有需要者可搭配食用

我又来了。。。

思路：

因为不同的小游戏不能准时完成时具有不同的扣款权数，而且是求问题的最优解，所以很容易想到用贪心算法求解。

贪心策略是让扣款数额大的尽量在规定的期限内完成，这样我们就先把这些任务按照扣款的数额进行排序，把大的排在前面，进行放置。

假如罚款最多的一个任务的完成期限是k，我们应该放在小于等于k的最靠后的时间段。

一旦出现一个不可能在规定期限内完成的任务，则把其扔到最大的一个空时间段，因为不能完成的任务在任意一个时间段中罚款数额都是一样的，这样得到的结果必然是最优的。

时间复杂度:O(n^2)

by 一本通

#include<cstdio>
#include<algorithm>
using namespace std;
int hash[5000001]; 
struct ben
{
    int x,y;
}a[501];
int cmp(const ben &a,const ben &b)
{
    return a.y>b.y;
}
int main()
{
    int m,n;
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i].x);//完成期限
    for(int i=1;i<=n;i++)scanf("%d",&a[i].y);//罚款
    sort(a+1,a+n+1,cmp);//按照罚款数额从大到小进行选择排序
    int bj=0;
    int s=0;
    for(int i=1;i<=n;i++)
    {
        bj=1;
        for(int j=a[i].x;j>=1;j--)
        {
            if(hash[j]==0)
            {
                bj=0;
                hash[j]=1;
                break;
            }
        }
        if(bj==1)//要罚款
        {
            for(int k=n;k>=1;k--)
            {
                if(hash[k]==0)
                {
                    hash[k]=1;
                    break;
                }
            }
            s+=a[i].y;//累加罚款
        }
    }
    printf("%d",m-s);
    return 0;
}

只求二事：

过和赞