Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

这个贪心。。。。。。

Posted by lvweihua at 2017-08-10 14:30:13 on Problem 3040
#include<cstdio>                             //该题是由硬币问题衍生出的更高级的贪心问题
#include<cstring>                            //硬币选取的方式与之前的一样
#include<algorithm>
using namespace std;
const long INF=0x3f3f3f;
const int MAXN=35;
int use[MAXN];                               //记录当前取法的第i种面值取的个数
struct Coin{
    int b,v;
}coin[MAXN];
int cmp(const Coin &a,const Coin &b){
    return a.v<b.v;
}
int main()
{
    int N,C,m;
    while(scanf("%d%d",&N,&C)!=EOF){
        for(int i=0;i<N;i++)
            scanf("%d%d",&coin[i].v,&coin[i].b);
        sort(coin,coin+N,cmp);
        int ans=0;
        for(int i=N-1;i>=0;i--){            //只要面值大于C的纸币,都可以一次性支付
            if(coin[i].v>=C){
                ans+=coin[i].b;
                coin[i].b=0;
            }
        }
        while(true){                        //每次循环寻找一个当前最优的走法,直到剩下的总金额小于C
            int sign=0;                     //是否找到合适的选取方式的标记
            long cnt=C;
            memset(use,0,sizeof(use));
            for(int i=N-1;i>=0;i--){        //第二步,从大到小取,不能超过C的面值
                if(coin[i].b){              //可以选择当前纸币
                    int k=cnt/coin[i].v;
                    m=min(k,coin[i].b);     //尽可能地使用大面额的纸币
                    cnt-=m*coin[i].v;
                    use[i]=m;
                    if(cnt==0){
                        sign=1;break;       //已经找到足够的金币了,直接退出
                    }
                }
            }
            if(cnt>0){
                for(int i=0;i<N;i++){       //从小到大选取
                    while(coin[i].b>use[i]){
                        cnt-=coin[i].v;
                        use[i]++;
                        if(cnt<=0){
                            sign=1;break;
                        }
                    }
                    if(sign)break;
                }
            }
            if(!sign)break;
            m=INF;
            for(int i=0;i<N;i++){
                if(use[i])                  //找到当前取法能取的总次数
                    m=min(m,coin[i].b/use[i]);
            }
            ans+=m;
            for(int i=0;i<N;i++){
                if(use[i])
                    coin[i].b-=m*use[i];
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator