自动搬运

查看原文

来自洛谷，原作者为

	ShineEternal **

搬运于2025-08-24 21:22:41，当前版本为作者最后更新于2018-07-22 17:30:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言：

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

题目链接:

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;
}

只求二事：

过和赞