零用钱“编程题”

2169 零用钱
时间限制: 1 s
空间限制: 32000 KB
题目等级 : 黄金 Gold
题解
查看运行结果
题目描述 Description
作為创造產奶纪录的回报，Farmer John决定开始每个星期给Bessie一点零花钱。

FJ有一些硬币，一共有N (1 <= N <= 20)种不同的面额。每一个面额都能整除所有比它大的面额。

他想用给定的硬币的集合，每个星期至少给Bessie某个零花钱的数目C (1 <= C <=
100000000)。请帮他计算他最多能支付多少个星期的零花钱。

输入描述 Input Description
第一行: 两个由空格隔开的整数: N 和 C

第2到第N+1行: 每一行有两个整数表示一个面额的硬币：硬币面额V (1 <= V <=
100,000,000)和Farmer John拥有的该面额的硬币数B (1 <= B <=
1,000,000).

输出描述 Output Description
第一行: 一个单独的整数，表示Farmer John最多能给Bessie支付多少个星期至少為C的零用钱。

样例输入 Sample Input
3 6
10 1
1 100
5 120

样例输出 Sample Output
111

数据范围及提示 Data Size & Hint
FJ想要每个星期给Bessie六美分。他有100个1美分硬币，120个5美分硬币，和一个10美分硬币。

FJ可以在一个星期超额付给Bessie一个10美分硬币。然后接下来的10个星期每星期付给
Bessie两个5美分硬币。最后100个星期每星期付给Bessie一个1美分硬币跟一个5美分硬
币。

emmmmm
一个好想不好写的贪心

从最大的开始给，不够再添小的
这样可以防止小的给完了，只能用大的相互凑，造成巨大浪费的情况
选取顺序： 最大 - > 最小
添补顺序： 最小 -> 最大

#include 
#include 
#include 
#include 
using namespace std;
const int MAXN = 35;
int n,c,ans = 0;
struct edge{
    int v,b;
}l[MAXN];

bool cmp(edge a,edge b){
    return a.v < b.v;
}

int main(){
    freopen("money.in","r",stdin);
    freopen("money.out","w",stdout);
    memset(l,0,sizeof(l));
    scanf("%d %d",&n,&c);
    for(int i = 1; i <= n; i ++){
        scanf("%d %d",&l[i].v,&l[i].b);
        if(l[i].v >= c) ans += l[i].b,l[i].b = 0;
    }
    sort(l + 1,l + n + 1,cmp);

    while(true){
        int now = 0;
        for(int i = n; i >= 1; i --)
            while(l[i].v + now < c && l[i].b)
                now += l[i].v,l[i].b --; 
        for(int i = 1; i <= n; i ++){
            if(!l[i].b) continue;
            now += l[i].v; l[i].b --;
            break;
        }
        if(now >= c) ans ++;
        else break;
    }

    printf("%d\n",ans);
    fclose(stdin); fclose(stdout);
    return 0;
}