首页 > 代码库 > codeforces #407(div1c div 2e)The Great Mixing
codeforces #407(div1c div 2e)The Great Mixing
给出k瓶可乐，浓度为ai/1000,输出最少用多少瓶才能配出浓度为n的可乐？
分析：显然，每个浓度对最终浓度的贡献是ai-n,如果最终总和贡献为0的时候，那就是一个答案
那么，浓度贡献的范围是[-1000,1000],+1000映射到[0,2000]，
只要关心每一个贡献出现的时候最少多少瓶就Ok了
bfs搜一发
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=1e4+5; 4 int n,k; 5 6 int a[maxn],b[maxn],v,tot=0; 7 8 queue<int> q; 9 10 int main(){11 scanf("%d%d",&n,&k);12 13 for(int i=0;i<k;i++){14 scanf("%d",&v);15 a[v]=1;16 }17 18 if(a[n]==1){19 puts("1");20 return 0;21 }22 23 24 25 for(int i=0;i<=1000;i++)if(a[i]==1){26 b[tot++]=i;27 q.push(i-n+1001);28 }29 30 for(int i=0;i<tot;i++)a[b[i]-n+1001]=1;31 32 while(!q.empty()){33 int val=q.front();q.pop();34 val-=1001;35 36 for(int i=0;i<tot;i++){37 int vv=val+b[i]-n;38 39 if(vv==0){40 printf("%d\n",a[val+1001]+1);41 return 0;42 }43 vv+=1001;44 if(vv<0)45 {46 continue;47 }48 if(!a[vv]){49 a[vv]=a[val+1001]+1;50 q.push(vv);51 }52 }53 }54 55 56 puts("-1");57 58 59 60 61 return 0;62 }
codeforces #407(div1c div 2e)The Great Mixing
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。