题目描述
大家一定觉得运动以后喝可乐是一件很惬意的事情,但是seeyou却不这么认为。因为每次当seeyou买了可乐以后,阿牛就要求和seeyou一起分享这一瓶可乐,而且一定要喝的和seeyou一样多。但seeyou的手中只有两个杯子,它们的容量分别是N 毫升和M 毫升 可乐的体积为\(S (S < 101)\)
毫升 (正好装满一瓶) ,它们三个之间可以相互倒可乐 (都是没有刻度的,且\(S==N+M,101>S>0,N>0,M>0\)) 。聪明的OIER你们说他们能平分吗?如果能请输出倒可乐的最少的次数,如果不能输出"NO"。
输入
三个整数 : S 可乐的体积 , N 和 M是两个杯子的容量,以"0 0 0"结束。
输出
如果能平分的话请输出最少要倒的次数,否则输出"NO"。
样例输入
7 4 3
4 1 3
0 0 0
样例输出
NO
3
代码
(不得不说好难啊)
#include <bits/stdc++.h>
using namespace std;
int vis[105][105][105];
int v[3];//可乐瓶和两个杯子的容量
int s,n,m,flag;
struct node{
int coke[3];//可乐瓶和两个杯子当前的量
int s;//倒的次数
};
void bfs()
{
int avg=v[0]/2;
memset(vis,0,sizeof(vis));
flag=0;
queue<node> q;
node temp;
temp.coke[0]=v[0];
temp.coke[1]=0;
temp.coke[2]=0;
temp.s=0;
vis[v[0]][0][0]=1;
q.push(temp);
while(!q.empty())
{
temp=q.front();
q.pop();
if((temp.coke[0]==avg&&temp.coke[1]==avg)||(temp.coke[0]==avg&&temp.coke[2]==avg)||(temp.coke[1]==avg&&temp.coke[2]==avg))
{
cout << temp.s << endl;
flag=1;
break;
}
//i杯子中的可乐往j中倒
for(int i=0;i<3;i++)
{//6种方案:0➡1 0➡2 1➡0 1➡2 2➡0 2➡1
for(int j=0;j<3;j++)
{
if(i==j) continue;//自己不能给自己倒
node tmp=temp;
int pour=min(tmp.coke[i],v[j]-tmp.coke[j]);//取杯子i中的剩余可乐和杯子j中的剩余容量最小值
tmp.coke[j]+=pour;
tmp.coke[i]-=pour;
if(!vis[tmp.coke[0]][tmp.coke[1]][tmp.coke[2]])
{
vis[tmp.coke[0]][tmp.coke[1]][tmp.coke[2]]=1;
tmp.s++;
q.push(tmp);
}
}
}
}
if(!flag) cout << "NO\n";
}
int main()
{
while(cin >> v[0] >> v[1] >> v[2]&&(v[0]||v[1]||v[2]))
{
if(v[0]%2==1)
{
cout << "NO\n";
continue;
}
bfs();
}
return 0;
}
原文链接:https://www.cnblogs.com/momotrace/p/very-cola.html
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:非常可乐 - Python技术站