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

题目传送门。

原文食用效果更佳。

题意

给定 n 和 k，表示有 n 种面值和 k 元，给定每种硬币的面值和是否收藏。

求用 k 元能够得到多少种还没有过的硬币，在满足上这一问的前提下，能够买的最贵的商品是什么。

分析

这是一道贪心题，主要注意几点：

首先，找到所有未收藏硬币面值里最小的，因为它们总是比面值大的硬币价值高。

其次，不能不买东西，一定要购买至少一种面值的硬币。

接着，硬币面值数据按照递增输入，无需排序。

然后，当这种硬币的面值大于当前所有的钱(找回的钱)时，不能买，钱不够(总不能抢吧)。

最后，不能重复购买同一种面值的硬币，每种只能买一次，否则会出错。

Code

#include<bits/stdc++.h>
using namespace std;
int f[50007];
int n, k, x, y, p, t;
int main() {
    scanf ("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf ("%d%d", &x, &y);
        // 找钱可以收藏此面值的硬币
        if (p >= x) {
            // 找钱减去当前这种硬币的面值
            p -= f[t];
            // 从 f 数组里删除这种面值的硬币
            t--;
            f[t] = 0;
        }
        // 没收藏过
        if (y == 0) {
            // 当前找钱超过了手中的钱，跳出循环
            if (x + p >= k)
                break;
            // 找钱加上当前硬币面值
            p += x;
            // 能获得之前没有的面值硬币数量加1
            t++;
            // 将当前这种硬币的面值存进 f 数组，表示收藏了
            f[t] = x;
        }
    }
    // 如果找钱为0，则找钱为1，不然就 91 分
    if (p == 0)
        p = 1;
    printf ("%d\n%d", t, k - p);
    return 0;
}

91 分记录。

AC 记录。

完结撒花。

作者写题解不易，点个赞再走呗。