洛谷 P2376 [USACO09OCT]津贴Allowance 题解【贪心】【快速排序】

点击量：150

   贪心大毒瘤。。。

目录

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 compute the maximum number of weeks he can pay Bessie.

作为对勤勤恳恳工作的贝茜的奖励，约翰已经决定开始支付贝茜小小的每周津贴。约翰有N(1≤N≤20)种币值的硬币，面值小的硬币总能整除面值较大的硬币。比如说，币值有如下几种：1美分，5美分，10美分，50美分…

   

利用给定的这些硬币，他将要每周付给贝茜一定金额的津贴C(1≤C≤10^8)。

   

请帮他计算出他最多能给贝茜发几周的津贴。

Input

第1行：两个用空格隔开的整数N和C。

   

第2到N+1行：每行两个整数表示一种币值的硬币。第一个整数V(1≤V≤10^8)，表示币值。

   

第二个整数B(1≤B≤10^6)，表示约翰拥有的这种硬币的个数。

Output

一个整数，表示约翰付给贝茜津贴最多的周数。

Sample Input

3 6
10 1
1 1 00
5 1 20

Sample Output

111

HINT

约翰想要每周付给贝茜6美分。他有1个10美分的硬币、100个1美分的硬币、120个5美分的硬币。约翰可以第一周付给贝茜一个10美分的硬币，接着的10周每周付给贝茜2个5美分硬币，接下来的100周每周付给贝茜一个1美分的硬币和1个5美分的硬币．共计111周。

Code：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using std::pair;
int sum=0;
pair<int,int> p[22];
int Div(int x,int y)//除法并向上取整，用于计算当前可用次数
{
    return x/y+(x%y>0);
}
int use[22];
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)//first是钱币面值，second是钱币张数
        scanf("%d%d",&p[i].first,&p[i].second);
    std::sort(p+1,p+1+n);//从小到大排序
    while(p[n].first>=k)//当面值大于要发的钱数时，直接花掉
    {
        sum+=p[n].second;
        n--;
    }
    while(1)
    {
        memset(use,0,sizeof(use));//use是当前应该使用的次数
        if(p[n].second==0)
            n--;
        int tmp=0;
        for(int i=n;i>=1;i--)
        {
            if(p[i].second==0)
                continue;
            int delta=k-tmp;//还差多少
            int d=delta/p[i].first;//应该提供多少
            if(d<=p[i].second)//在提供范围内
            {
                use[i]+=d;
                tmp+=d*p[i].first;
            }
            else
            {
                use[i]+=p[i].second;
                tmp+=p[i].second*p[i].first;
            }
        }
        for(int i=1;i<=n&&tmp<k;i++)//从小到大算
        {
            if(p[i].second-use[i]==0)
                continue;
            int delta=k-tmp;
            int d=Div(delta,p[i].first);
            if(p[i].second-use[i]>=d)
            {
                use[i]+=d;
                tmp+=d*delta;
            }
            else
            {
                use[i]=p[i].second;
                tmp+=(p[i].second-use[i])*p[i].first;//use是第一步已经用了的
            }
        }
        if(tmp<k)
            break;
        int mn=999999999;
        for(int i=1;i<=n;i++)
        {
            if(!use[i])
                continue;
            int d=p[i].second/use[i];
            mn=mn<d?mn:d;
        }
        for(int i=1;i<=n;i++)
            p[i].second-=use[i]*mn;
        sum+=mn;
    }
    printf("%d\n",sum);
    return 0;
}