Tyvj1032

题目链接

分析：
显然，比c面值大的钱，我们直接给就好了
那么问题就变成了，有一堆比c面值小的硬币，
让我们凑出尽量多的c

正当我苦于c的范围无法承受01背包时
我又看了一遍题面，发现了这句话：
每一个面额都能整除所有比它大的面额

这句话好像非常的关键
也就是说，大面值的钱能做到的事，比ta小的硬币都能做到

显然我们要是能凑出c的钱数
就不要给奶牛贝西大于c的钱

优先选用面值大的钱（直觉告诉我）
看来就是个贪心，但是我贪不出来啊

一开始一直在想一些简便的算法，可以很快的求出来

但是怎么弄都有缺陷
（比如说：把所有面值大的硬币能用的就用，但是万一像样例中那样每天给两个5块怎么处理呢）

后来才发现一天一天的贪心模拟就可以了
无fuck说。。。

这里写代码片
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long

using namespace std;

int n,tot;
int c;
struct node{
    ll v,num;
};
node a[30];
int ans,use[30],q[30][2],tou,wei;
int sum;

int cmp(const node &x,const node &y)
{
    return x.v<y.v;
}

void doit()
{
    int i,j,k;
    int cc=0;
    bool ff=1;
    while (ff)
    {
        cc=c;
        for (i=tot;i>=1;i--)
            while (a[i].v<=cc&&a[i].num)
            {
                cc-=a[i].v;
                a[i].num--;
            }
        if (cc)
            for (i=1;i<=tot;i++)   //不够的尽量用小的去补 
                while (a[i].num&&cc>0)
                {
                    cc-=a[i].v;
                    a[i].num--;
                    if (cc<0) break;   
                }
        if (cc>0) ff=0;
        else ans++;
    }
    printf("%d",ans);
}

int main()
{
    scanf("%d%d",&n,&c);
    for (int i=1;i<=n;i++) 
    {
        int u,w;
        scanf("%d%d",&u,&w);
        if (u>=c) ans+=w;
        else
        {
            tot++;
            a[tot].v=u; a[tot].num=w;
        }
    }
    sort(a+1,a+1+tot,cmp);
    doit();
    return 0;
}