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

作者: wjyyy 分类: 快速排序,解题报告,贪心 发布时间: 2018-07-01 16:12

点击量:14

 

   贪心大毒瘤。。。

 

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周。
   题目没有理解难度,因此可以看得出是个贪心,不过贪心怎么贪就是问题了。
   
   因为面值比要给的钱还多时,只给一张是最优的,所以这些我们直接处理:加上这些钱币的数目。
   
   当最大面值不够要给的钱时,我们就要来凑。因为前面的数总能整除后面的数,那么我们可以推出,对于第k个数(设\(a_i\)为第i张钱币的面值):\(\sum_{i=1}^{k-1}a_i<a_k\)
   
   那么我们给得尽可能多,为了不浪费,如果可以用\(a_1~a_{k-1}\)来凑到的话,就不需要浪费\(a_k\)了,这样如果使用前面的,会比\(a_k\)浪费得更少。如果前面凑不够了,再回来用\(a_k\),此时可以证明所有钱币用完了。
   
   那么我们的策略就是,先从大到小选,设我们已经选的是x,目标为y,当x+ai≤y时,我们可以将ai选上,这样不造成浪费。而当x+ai>y时,就暂时不选,因为后面有可能有更优秀的组合方式,使得浪费尽可能少。
  
   而当i遍历到1,如果x+ai刚好等于y,那么就统计可以使用这个方案的次数,把这些钱币数全部减掉,从而做到加速这个进程,降下时间复杂度。如果还是不能使得x+ai刚好等于y,那么再从小到大枚举ai,如果ai有多张,那么就把这些钱全部凑上,直到凑够。如果凑不够,那么再使i++,继续进行上一步操作。
   
   因为我们要求尽可能少浪费,这样就可以发更多的津贴,那么少浪费意味着最终的x-y要尽可能小。所以我们在未到达的前提下,选择的钱币尽可能大而不越界,越界后,在缩小差距的前提下,选择的钱币要尽可能小。

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;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */