POJ：3040-Allowance（贪心好题）

Allowance

Time Limit: 1000MS Memory Limit: 65536K

Total Submissions: 4903 Accepted: 1943

Description

As a reward for record milk production, Farmer John has decided to start paying Bessie the cow a small weekly allowance. FJ has a set of coins in N (1 <= N <= 20) different denominations, where each denomination of coin evenly divides the next-larger denomination (e.g., 1 cent coins, 5 cent coins, 10 cent coins, and 50 cent coins).Using the given set of coins, he would like to pay Bessie at least some given amount of money C (1 <= C <= 100,000,000) every week.Please help him ompute the maximum number of weeks he can pay Bessie.

Input

Line 1: Two space-separated integers: N and C
Lines 2..N+1: Each line corresponds to a denomination of coin and contains two integers: the value V (1 <= V <= 100,000,000) of the denomination, and the number of coins B (1 <= B <= 1,000,000) of this denomation in Farmer John’s possession.

Output

Line 1: A single integer that is the number of weeks Farmer John can pay Bessie at least C allowance

Sample Input

3 6

10 1

1 100

5 120

Sample Output

111

Hint

INPUT DETAILS:

FJ would like to pay Bessie 6 cents per week. He has 100 1-cent coins,120 5-cent coins, and 1 10-cent coin.

OUTPUT DETAILS:

FJ can overpay Bessie with the one 10-cent coin for 1 week, then pay Bessie two 5-cent coins for 10 weeks and then pay Bessie one 1-cent coin and one 5-cent coin for 100 weeks.

解题新的：

题意就是你有很多张面额不同的纸币，你每个星期要给奶牛至少c元，问你用现在的钱最多给奶牛多少周。
这个题的感觉就是贪心，想了两三种方案感觉都不太对，后来发现这真的是很好的一个题，首先，将大于等于c的面额的钱直接每个星期给奶牛一张，将面额大于等于c的前去除，然后从大到小开始选择，要选择的金额尽可能的接近c，如果刚好能够凑足c就作为当前的一种方案，如果不能凑足c那就再从小的开始选，要选出一种的总额不少于c但尽量接近c作为当前的方案，然后计算如果按照如此方案最多可以给奶牛多少周，然后按照相同的方法再选方案，一直选到选择的金额不能凑足c为止。
为啥可以用这中方法，首先，这个题的数据量给你很大的提示，纸币的面额最多20种，然后排除起它比较简单的贪心思维，简单的从大到小，从小到大什么的，然后将从大到小，从小到大结合起来。

#include <stdio.h>

#include <algorithm>

#include <cstring>

using namespace std;

typedef long long ll;

const int maxn = 25;

struct MONEY {

    ll va,num;

}m[maxn];

ll ans = 0,n,c;

ll use[maxn];

bool cmp(MONEY a,MONEY b) {

    return a.va < b.va;

}

void init() {

    scanf("%d%d",&n,&c);

    for(int i=0;i<n;i++)

        scanf("%d%d",&m[i].va,&m[i].num);

    sort(m,m+n,cmp);

}

int main() {

    init();

    bool flag;

    for(int i=n-1;i>=0;i--) {

        if(m[i].va  >= c) {

            ans += m[i].num;

            m[i].num = 0;

        }

    }

    while(true) {

        memset(use,0,sizeof(use));

        flag = false;

        ll temp_c = c,M;

        for(int i=n-1;i>=0;i--) {

            if(m[i].num) {

                ll num = temp_c / m[i].va;

                M = min(num,m[i].num);

                temp_c -= M*m[i].va;

                use[i] = M;

                if(temp_c == 0) {

                    flag = true;

                    break;

                }

            }

        }

        if(temp_c > 0) {

            for(int i=0;i<n;i++) {

                if(m[i].num > use[i]) {

                    while(use[i] < m[i].num) {

                        temp_c -= m[i].va;

                        use[i]++;

                        if(temp_c < 0) {

                            flag = true;

                            break;

                        }

                    }

                }

                if(flag)

                    break;

            }

        }

        if(!flag)

            break;

        ll cnt = 0x7f7f7f7f;

        for(int i=0;i<n;i++) {

            if(use[i])

                cnt = min(cnt,m[i].num/use[i]);

        }

        ans += cnt;

        for(int i=0;i<n;i++)

            m[i].num -= use[i]*cnt;

    }

    printf("%d\n",ans);

    return 0;

}

巴特西