poj3040 貪心

此題題意如下：

有n種硬币，并且硬币是按照一定次序排列的如：1，5，10，50。。。 網上說是這個次序導緻它可以如此貪心的

然後有一個人要給他的牛錢，每周一點數量c，每次給的話必須大于等于c

給你一定數量的各種錢，讓你求最長的周數。

此貪心解釋如下：

1：大于c的就直接取；

2：如果小于就從大到小拿錢，能拿多少拿多少，但不能超過c；

3：如果2拿的錢小于c，就從小到大拿錢，能拿多少拿多少，但要求是超過c的時候是最小的，也就是說，這些錢的總和是大于c的最小數；

4：将此類取錢方式求出次數，加到count中，然後傳回第二步。

那麼代碼如下：

#include <cstdio>
#include <cstring>
#include <algorithm>

#define v first
#define b second

using namespace std;

typedef pair<int, int> node;

bool cmp(node num1, node num2)
{
    return num1.v > num2.v;
}

int main()
{
    int n, c;
    node val[];
    scanf("%d%d", &n, &c);
    for (int i = ; i < n; ++i)
    {
        scanf("%d%d", &val[i].v, &val[i].b);
    }
    sort(val, val + n, cmp);    //從大到小排序

    int i = ;
    int count = ;
    for (; i < n; ++i)    //完全大于c的就直接用
    {
        if (val[i].v >= c)
        {
            count += val[i].b;
            val[i].b = ;
        }
        else break;
    }

    int need[] = {};   //記錄每次你用了多少種coin
    while()
    {
        int sum = c;
        memset(need, , sizeof need);
        for (int j = i; j < n; ++j)  //先從大到小取，但不要超過c
        {
            if (val[j].b && sum > )
            {
                need[j] += min(val[j].b, sum / val[j].v);//取最小的個數
                sum -= need[j] * val[j].v;//減去已用了的
            }
        }

        if (sum > )
        {
            for (int j = n - ; j >= i; --j)  //如果上面那次取法不夠，就從小往大找補替，這樣保證是最小損失
            {
                if (val[j].b && sum > )
                {
                    int mi;
                    mi = min(val[j].b - need[j], (sum + val[j].v - ) / val[j].v);
                    if(mi > )   //這兒有可能是負數
                    {
                        sum -= mi * val[j].v;
                        need[j] += mi;
                    }
                }
            }
        }

        if (sum > ) break;   //如果已經不夠了，退出循環

        int x =  + ;
        for (int j = i; j < n; ++j)
        {
            if(need[j])
            {
                x = min(val[j].b / need[j], x);//取最小的每次需要的種類的次數
            }
        }

        count += x;
        for (int j = i; j < n; ++j)
        {
            if (need[j])
            {
                val[j].b -= x * need[j];//将用過的删除
            }
        }
    }
    printf("%d\n", count);

    return ;
}