自动搬运

查看原文

来自洛谷，原作者为

	fallen_leaves 无条件支持互关

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

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

以下是正文

P7638 [BalticOI 2006] COIN COLLECTOR (Day 1)

题意

有一个硬币收藏家，他有一张 $K$ 分的纸币，他去一家商店买硬币，这些硬币的价格都小于 $K-1$ 分，每一次都会按一下方式找钱。

• 假设要找 $A$ 分钱。
• 找到一枚不高于 $A$ 分钱的硬币 $B$。
• 给他 $B$ 硬币，让 $A$ 减去 $B$。
• 如果钱找完了，结束；否则返回第二步。

这个硬币收藏家只用 $K$ 分纸币买一件东西，问你两个问题：他新获得了多少以前没有的种数？他在这种情况下，商店能卖给他的最贵商品。

思路

首先我们考虑贪心，我们可以采用逆向思维，因为这个人想拥有之前没有用过的硬币，越多越好，所以我们主要考虑没有拥有的，我们可以从小到大依次寻找没有拥有过的硬币，但如果我拥有了 $2$ 和 $3$ 分这两枚硬币，又遇到了一枚 $4$ 分硬币，那么 $2$ 和 $3$ 这两枚就必须有一枚不要，我们不需要考虑以前拥有过的硬币，因为文中讲了需要找到一枚不高于 $A$ 分钱的硬币 $B$，所以不论买没买过都需要拿。

我们还要考虑一种特殊情况，就是所有硬币他都拥有了，那么答案的第一问就是 $0$，因为最贵的硬币就是 $K-1$，所以第二问就是 $K-1$。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int v,f,sum,d[500005],idx,k,n;
signed main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>v>>f;
		if(sum>=v)//因为每次是选最接近K的数，所以肯定会扔掉一枚硬币
		{
			sum-=d[idx];
			idx--;
		}
		if(!f)//该硬币没被收藏
		{
			if(v+sum>=k) break;
			sum+=v;
			d[++idx]=v;//该硬币应该是被找钱的
		}
	}
	if(!sum) sum=1;
	cout<<idx<<endl<<k-sum;
	return 0;
}