首页 > 代码库 > HDU - 1495 - 非常可乐
HDU - 1495 - 非常可乐
线上题目：
非常可乐
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4482 Accepted Submission(s): 1815
Problem 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即可，广搜的时候需要记录的是当前的三个杯子的状态，然后判定一下重复就可以了。这里用set保存已经进行扩展了的状态。
上代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <set> 5 #include <queue> 6 #include <utility> 7 #define x first 8 #define y second 9 using namespace std; 10 11 typedef pair<pair<int,int>,int> piii; 12 int s,n,m,ti; 13 14 set<piii> ss; 15 16 bool isok(piii a){ 17 if(a.x.x*2==s && a.x.y*2==s) return 1; 18 else if(a.x.x*2==s && a.y*2==s) return 1; 19 else if(a.x.y*2==s && a.y*2==s) return 1; 20 return 0; 21 } 22 23 inline piii mpiii(int a,int b,int c) { return make_pair( make_pair(a,b) , c ); } 24 25 bool check(){ 26 ti=0; 27 queue<pair<piii,int> > q; 28 pair<piii,int> tt; 29 piii u = mpiii(s,0,0); 30 q.push(make_pair(u,0)); 31 ss.insert(u); 32 while(!q.empty()){ 33 int tti; 34 tt = q.front(); 35 q.pop(); 36 u = tt.x; 37 tti = tt.y; 38 //s-->n 39 if(u.x.x>0 && (n-u.x.y)>0){ 40 if( u.x.x > (n-u.x.y) ){ u.x.x-=(n-u.x.y); u.x.y=n; } 41 else{ u.x.y+=u.x.x; u.x.x=0; } 42 if(ss.count(u)<=0){ 43 tti++; 44 if(isok(u)){ti=tti; return 1;} 45 ss.insert(u); 46 q.push( make_pair(u,tti) ); 47 } 48 } 49 //s-->m 50 u = tt.x; 51 tti = tt.y; 52 if(u.x.x>0 && (m-u.y)>0){ 53 if( u.x.x > (m-u.y) ){ u.x.x-=(m-u.y); u.y=m; } 54 else{ u.y+=u.x.x; u.x.x=0; } 55 if(ss.count(u)<=0){ 56 tti++; 57 if(isok(u)){ti=tti; return 1;} 58 ss.insert(u); 59 q.push( make_pair(u,tti) ); 60 } 61 } 62 //n-->s 63 u = tt.x; 64 tti = tt.y; 65 if(u.x.y>0 && (s-u.x.x)>0){ 66 if( u.x.y > (s-u.x.x) ){ u.x.y-=(s-u.x.x); u.x.x=s; } 67 else{ u.x.x+=u.x.y; u.x.y=0; } 68 if(ss.count(u)<=0){ 69 tti++; 70 if(isok(u)){ti=tti; return 1;} 71 ss.insert(u); 72 q.push( make_pair(u,tti) ); 73 } 74 } 75 //n-->m 76 u = tt.x; 77 tti = tt.y; 78 if(u.x.y>0 && (m-u.y)>0){ 79 if( u.x.y > (m-u.y) ){ u.x.y-=(m-u.y); u.y=m; } 80 else{ u.y+=u.x.y; u.x.y=0;} 81 if(ss.count(u)<=0){ 82 tti++; 83 if(isok(u)){ti=tti; return 1;} 84 ss.insert(u); 85 q.push( make_pair(u,tti) ); 86 } 87 } 88 //m-->s 89 u = tt.x; 90 tti = tt.y; 91 if(u.y>0 && (s-u.x.x)>0){ 92 if( u.y > (s-u.x.x) ){ u.y-=(s-u.x.x); u.x.x=s; } 93 else{ u.x.x+=u.y; u.y=0; } 94 if(ss.count(u)<=0){ 95 tti++; 96 if(isok(u)){ti=tti; return 1;} 97 ss.insert(u); 98 q.push( make_pair(u,tti) ); 99 }100 }101 //m-->n102 u = tt.x;103 tti = tt.y;104 if(u.y>0 && (n-u.x.y)>0){105 if( u.y > (n-u.x.y) ){ u.y-=(n-u.x.y); u.x.y=n; }106 else{ u.x.y+=u.y; u.y=0; }107 if(ss.count(u)<=0){108 tti++;109 if(isok(u)){ti=tti; return 1;}110 ss.insert(u);111 q.push( make_pair(u,tti) );112 }113 }114 }115 return 0;116 }117 118 int main()119 {120 //freopen("data.txt","r",stdin);121 while(scanf("%d %d %d",&s,&n,&m),(s+n+m)){122 ss.clear();123 if( (s&1)==0 && check()) printf("%d\n",ti);124 else printf("NO\n");125 }126 return 0;127 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。