HUT1694 零用钱 贪心

这题真的要设身处地为该题想一想才能感受到这一贪心规则，题目是要求用所给定的硬币，根据面值和数目求出能每天给出不少与C元的次数。

对于面值大于C的硬币，没有办法，我们只能够一次性给他们，但在这上面我们不许要再添加其他的硬币。

而对于比C小的硬币，我们应该让这些分散的硬币集合到一起，使得其组合值在大于或等于C的指导思想下无限接近于C，于是对于这些硬币我就不停的塞硬币，这一次不能够超过C的值，当然我们优先会塞面值大的，因为这些硬币是不可分割的，小的硬币更具灵活性。在上一步之后，（如果没有塞到C的话）我们在考虑找一些硬币使得其值略微超过C，于是第二次我们从小的开始塞，而且一定是只塞一枚就会超过C。

代码如下：

#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
using namespace std;
 
int T, C;
 
struct Node
{
    int p, n;
    bool operator < (Node t) const
    {
        return p > t.p;
    }
}e[25];
 
void deal()
{
    int pos, ans = 0, finish = true, left, cnt, num;
    for (int i = 1; i <= T; ++i) {
        if (e[i].p >= C) {
            ans += e[i].n;
        }
        else {
            pos = i;
            finish = false;
            break;
        }
    }
    while (!finish) {
        finish = true;
        left = C;
        for (int i = pos; i <= T; ++i) { // 对于小于C的部分的组合方式
            if (e[i].n > 0 && e[i].p <= left) { 
                num = left / e[i].p;
                cnt = min(num, e[i].n);
                e[i].n -= cnt;
                left -= cnt*e[i].p;
            }
        }
        for (int i = T; i >= pos; --i) {
            if (e[i].n > 0 && left > 0) {
                --e[i].n;
                left-=e[i].p;
            }
        }
        if (left <= 0) {
            ++ans, finish = false;
        }
    }
    printf("%d\n", ans);
}
 
int main()
{
    while (scanf("%d %d", &T, &C) == 2) {
        for (int i = 1; i <= T; ++i) {
            scanf("%d %d", &e[i].p, &e[i].n);
        }
        sort(e+1, e+1+T);
        deal();
    }
    return 0;
}