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

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