题解：P7638 [BalticOI 2006] COIN COLLECTOR (Day 1)

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

。

CPP

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

题解：P7638 [BalticOI 2006] COIN COLLECTOR (Day 1)

文章操作

题意

思路

相关推荐

评论

题解：P7638 [BalticOI 2006] COIN COLLECTOR (Day 1)