网站工作室模板,免费发布信息网网站,网站建设管理及维护,贸易公司logo图片【题目描述】 大家一定觉的运动以后喝可乐是一件很惬意的事情#xff0c;但是seeyou却不这么认为。因为每次当seeyou买了可乐以后#xff0c;阿牛就要求和seeyou一起分享这一瓶可乐#xff0c;而且一定要喝的和seeyou一样多。但seeyou的手中只有两个杯子#xff0c;它们的容…【题目描述】 大家一定觉的运动以后喝可乐是一件很惬意的事情但是seeyou却不这么认为。因为每次当seeyou买了可乐以后阿牛就要求和seeyou一起分享这一瓶可乐而且一定要喝的和seeyou一样多。但seeyou的手中只有两个杯子它们的容量分别是N 毫升和M 毫升 可乐的体积为S S101毫升 (正好装满一瓶) 它们三个之间可以相互倒可乐 (都是没有刻度的且 SNM101S0N0M0) 。聪明的ACMER你们说他们能平分吗如果能请输出倒可乐的最少的次数如果不能输出NO。 Input 三个整数 : S 可乐的体积 , N 和 M是两个杯子的容量以0 0 0结束。 Output 如果能平分的话请输出最少要倒的次数否则输出NO。 Sample Input
7 4 3
4 1 3
0 0 0Sample Output
NO
3【题目分析】 看到最少的次数就应该想到应该是BFS,需要注意的是如何进行BFS以及如何标记已经访问过的状态。对于这道题我们可以用一个二维数组保存状态用两个循环来表示倒的过程进行枚举。注意杯子里面没有水是不能往出倒的然后还需要进行分类讨论 【AC代码】
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#includecmath
#includeclimits
#includestring
#includequeue
using namespace std;const int MAXN105;
int s,n,m,half;
int a[3];
struct node
{int tmp[3];int step;
}t,p;
int vis[MAXN][MAXN][MAXN];void BFS()
{a[0]s; a[1]n; a[2]m;queuenode q;memset(vis,0,sizeof(vis));p.tmp[0]s; p.tmp[1]0; p.tmp[2]0;p.step0;vis[s][0][0]1;q.push(p);while(!q.empty()){pq.front(); q.pop();for(int i0;i3;i){if(p.tmp[i]0){for(int j0;j3;j){tp;if(ij) continue;if(t.tmp[i]a[j]-t.tmp[j]){t.tmp[i]t.tmp[i]-a[j]t.tmp[j];t.tmp[j]a[j];}else{t.tmp[j]t.tmp[i];t.tmp[i]0;}if(!vis[t.tmp[0]][t.tmp[1]][t.tmp[2]]){vis[t.tmp[0]][t.tmp[1]][t.tmp[2]]1;t.step;if(t.tmp[0]halft.tmp[1]half || t.tmp[0]halft.tmp[2]half || t.tmp[1]halft.tmp[2]half){printf(%d\n,t.step);return;}q.push(t);}}}}}printf(NO\n);
}int main()
{while(~scanf(%d%d%d,s,n,m)(n || m || s)){if(s%2)//如果原本杯子里的水不是2的倍数肯定是无法分成相等的两部分的printf(NO\n);else{halfs/2;BFS();}}return 0;
}
