非常可乐
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 35881 Accepted Submission(s): 13963
Input 三个整数 : S 可乐的体积 , N 和 M是两个杯子的容量,以"0 0 0"结束。
Output 如果能平分的话请输出最少要倒的次数,否则输出"NO"。
Sample Input 7 4 3 4 1 3 0 0 0
Sample Output NO 3 AC代码
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<algorithm> #include<queue> using namespace std; struct node{ int cur[3]; int s; }p,t; int b[3],book[101][101][101];//别开的太大 int half=1; void bfs(); int main(){ //freopen("in.txt","r",stdin); while(cin>>b[0]>>b[1]>>b[2]&&(b[0] b[1] b[2])){ half=b[0]/2; p.cur[0]=b[0];p.cur[1]=0;p.cur[2]=0;p.s=0; memset(book,0,sizeof(book)); if(b[0]%2)cout<<"NO"<<endl; else bfs(); } return 0; } void bfs(){ queue<node> q; q.push(p); while(!q.empty()){ p=q.front(); for(int i=0;i<3; i){ if(p.cur[i]){ for(int j=0;j<3; j){ if(i==j)continue; if(p.cur[j]<b[j]){ t=p; if(p.cur[i]>=b[j]-p.cur[j]){ t.cur[i]-=(b[j]-p.cur[j]);t.cur[j]=b[j];t.s ; } else { t.cur[j] =p.cur[i];t.cur[i]=0;t.s ; } if(book[t.cur[0]][t.cur[1]][t.cur[2]]==0){ book[t.cur[0]][t.cur[1]][t.cur[2]]=1; q.push(t); } if((t.cur[0]==half&&t.cur[1]==half)||(t.cur[0]==half&&t.cur[2]==half)||(t.cur[1]==half&&t.cur[2]==half)){ cout<<t.s<<endl;return; } } } } } q.pop(); } cout<<"NO"<<endl; }