首页 > 代码库 > G - 非常可乐
G - 非常可乐
Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
Description
大家一定觉的运动以后喝可乐是一件很惬意的事情，但是seeyou却不这么认为。因为每次当seeyou买了可乐以后，阿牛就要求和seeyou一起分享 这一瓶可乐，而且一定要喝的和seeyou一样多。但seeyou的手中只有两个杯子，它们的容量分别是N 毫升和M 毫升 可乐的体积为S （S<101）毫升 (正好装满一瓶) ，它们三个之间可以相互倒可乐 (都是没有刻度的，且 S==N+M，101＞S＞0，N＞0，M＞0) 。聪明的ACMER你们说他们能平分吗？如果能请输出倒可乐的最少的次数，如果不能输出"NO"。
Input
三个整数 : S 可乐的体积 , N 和 M是两个杯子的容量，以"0 0 0"结束。
Output
如果能平分的话请输出最少要倒的次数，否则输出"NO"。
Sample Input
7 4 3 4 1 3 0 0 0
Sample Output
NO 3
简单的BFS，模拟倒水，（相当于枚举）
1 #include<cstdio> 2 #include<string.h> 3 using namespace std; 4 int s,n,m,pre[1000005][3],ans[1000005]; 5 int vis[120][120]; 6 int ans1; 7 void bfs() 8 { 9 int first=0,end=0,a,b,c; 10 pre[end][0]=s; 11 pre[end][1]=0; 12 pre[end++][2]=0; 13 vis[s][0]=1; 14 while(first<end) 15 { 16 a=pre[first][0]; 17 b=pre[first][1]; 18 c=pre[first][2]; 19 if((a==b&&c==0)||(a==c&&b==0)||(b==c&&a==0)) 20 { 21 ans1 =ans[first]; 22 return; 23 } 24 int a1,b1,c1; 25 if(a+b>=n) 26 { 27 a1=a+b-n; 28 b1=n; 29 c1=c; 30 } 31 else{ 32 b1=a+b; 33 a1=0; 34 c1=c; 35 } 36 if(vis[a1][b1]==0) 37 { 38 vis[a1][b1]=1; 39 pre[end][0]=a1; 40 pre[end][1]=b1; 41 pre[end][2]=c1; 42 ans[end++]=ans[first]+1; 43 } 44 if(a+c>=m) 45 { 46 a1=a+c-m; 47 c1=m; 48 b1=b; 49 } 50 else{ 51 c1=a+c; 52 a1=0; 53 b1=b; 54 } 55 if(vis[a1][b1]==0) 56 { 57 vis[a1][b1]=1; 58 pre[end][0]=a1; 59 pre[end][1]=b1; 60 pre[end][2]=c1; 61 ans[end++]=ans[first]+1; 62 } 63 if(b+a>=s) 64 { 65 a1=s; 66 b1=0; 67 c1=c; 68 } 69 else{ 70 a1=a+b; 71 b1=0; 72 c1=c; 73 } 74 if(vis[a1][b1]==0) 75 { 76 vis[a1][b1]=1; 77 pre[end][0]=a1; 78 pre[end][1]=b1; 79 pre[end][2]=c1; 80 ans[end++]=ans[first]+1; 81 } 82 if(b+c>=m) 83 { 84 b1=b+c-m; 85 c1=m; 86 a1=a; 87 } 88 else{ 89 c1=b+c; 90 b1=0; 91 a1=a; 92 } 93 if(vis[a1][b1]==0) 94 { 95 vis[a1][b1]=1; 96 pre[end][0]=a1; 97 pre[end][1]=b1; 98 pre[end][2]=c1; 99 ans[end++]=ans[first]+1;100 }101 if(c+a>=s)102 {103 a1=s;104 c1=0;105 b1=b;106 }107 else{108 a1=a+c;109 c1=0;110 b1=b;111 }112 if(vis[a1][b1]==0)113 {114 vis[a1][b1]=1;115 pre[end][0]=a1;116 pre[end][1]=b1;117 pre[end][2]=c1;118 ans[end++]=ans[first]+1;119 }120 if(c+b>=n)121 {122 c1=c+b-n;123 b1=n;124 a1=a;125 }126 else{127 b1=b+c;128 c1=0;129 a1=a;130 }131 if(vis[a1][b1]==0)132 {133 vis[a1][b1]=1;134 pre[end][0]=a1;135 pre[end][1]=b1;136 pre[end][2]=c1;137 ans[end++]=ans[first]+1;138 }139 first++;140 }141 142 }143 int main()144 {145 while(scanf("%d %d %d",&s,&n,&m)&&(s+n+m))146 {147 if(s%2)148 {149 printf("NO\n");150 continue;151 }152 ans1=0;153 memset(vis,0,sizeof(vis));154 bfs();155 if(ans1) printf("%d\n",ans1);156 else printf("NO\n");157 }158 return 0;159 }
G - 非常可乐
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。