贪心好题

……….

思路：

从大到小凑C 如果不够 再从小到大补满（超过）C

//By SiriusRen

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

int n,c,ans,flag,vis[21];

struct Money{int amount,value;}money[100];

bool cmp(Money a,Money b){return a.value<b.value;}

int main(){

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

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

        scanf("%d%d",&money[i].value,&money[i].amount);

    sort(money+1,money+1+n,cmp);

    while(1){

        memset(vis,0,sizeof(vis));

        int sum=c;

        for(int i=n;i;i--)

            if(sum>0&&money[i].amount){

                int temp=min(money[i].amount,sum/money[i].value);

                if(temp>0)sum-=money[i].value*temp,vis[i]+=temp;

            }

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

            if(sum>0&&money[i].amount&&money[i].value>=sum){

                sum-=money[i].value;vis[i]++;break;

            }

        if(sum>0)break;

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

            money[i].amount-=vis[i];

        ans++;

    }

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

}

卡时过得…

然后我发现 诶呦 一次可以同时消很多 然后就0msAC了,,,,

//By SiriusRen

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

int n,c,ans,flag,vis[21];

struct Money{int amount,value;}money[100];

bool cmp(Money a,Money b){return a.value<b.value;}

int main(){

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

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

        scanf("%d%d",&money[i].value,&money[i].amount);

    sort(money+1,money+1+n,cmp);

    while(1){

        memset(vis,0,sizeof(vis));

        int sum=c,temp=0x3ffffff;

        for(int i=n;i;i--)

            if(sum>0&&money[i].amount){

                int temp=min(money[i].amount,sum/money[i].value);

                if(temp>0)sum-=money[i].value*temp,vis[i]+=temp;

            }

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

            if(sum>0&&money[i].amount&&money[i].value>=sum){

                sum-=money[i].value;vis[i]++;break;

            }

        if(sum>0)break;

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

            if(!vis[i])continue;

            temp=min(temp,money[i].amount/vis[i]);

        }

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

            money[i].amount-=vis[i]*temp;

        }

        ans+=temp;

    }

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

}