自动搬运

查看原文

来自洛谷，原作者为

	a18981826590 **

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

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

以下是正文

P5961 [BalticOI 2006] coin collector钱币收藏家

解题思路

这道题可以使用贪心：先取未收藏的硬币中面值最小的，直到总硬币面值（即找钱）大于或等于（商品价格 $>0$）所带的纸币面值。但是，新取的硬币面值必须小于当前总硬币面值（因为商店找钱时先寻找最高的不超过需找钱面值的硬币）。同时，因为输入按照硬币面值递增顺序，所以当总硬币面值大于或等于所带的纸币面值就可以结束了。最后，如果总硬币面值为 $0$（所有硬币均已收藏），就应将找钱定为 $1$（商品价格 $<$ 所带的纸币面值）。

AC代码

#include<bits/stdc++.h>
using namespace std;
int a,b,c,d[500010],e,m,n;
int main(){
	scanf("%d%d",&n,&m);
	while(n--){
		scanf("%d%d",&a,&b);
		if(c>=a){
			c-=d[e];
			d[e--]=0;
		}
		if(!b){
			if(a+c>=m) break;
			c+=a;
			d[++e]=a;
		}
	}
    if(!c) c=1;
	printf("%d\n%d",e,m-c);
	return 0;
}