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

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