首页 > 代码库 > HDU 1495 <非常可乐>
HDU 1495 <非常可乐>
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 Input7 4 34 1 30 0 0
Sample OutputNO3
Authorseeyou
Source“2006校园文化活动月”之“校庆杯”大学生程序设计竞赛暨杭州电子科技大学第四届大学生程序设计竞赛
RecommendLL
题意：小学奥数。。
题解：搜索吧。总共就那几种操作。
#include<stdio.h>#include<queue>#include<set>using namespace std;int main(){ queue<long long>q; set<long long>p; long long d,a0,b0,c0,a,b,c,s, m, n,judge; long long t; while (scanf("%lld%lld%lld", &s, &m, &n) != EOF&&s) { judge = 0; //if (m > s)m = s;if (n > s)n = s; while (q.empty() != 1)q.pop(); p.clear(); d = 0;a = s;b = 0;c = 0; q.push(a * 1000 * 1000 + b * 1000 + c); p.insert(a * 1000 * 1000 + b * 1000 + c); while (q.size()) { t = q.front(); q.pop(); d = t / 1000 / 1000 / 1000; a = (t / 1000 / 1000)%1000; b = (t / 1000)%1000; c = t % 1000; //printf("%d %d %d %d\n",d,a,b,c); if ((a == b&&c == 0) || (a == c&&b == 0) || (b == c&&a == 0)) { judge = d; break; }; if ((n - b) >= a) { b0 = b + a;a0 = 0;c0 = c; } else { b0 = n;a0 = a - (n - b);c0 = c; } if (p.count(a0 * 1000 * 1000 + b0 * 1000 + c0) == 0) { p.insert(a0 * 1000 * 1000 + b0 * 1000 + c0); q.push((d+1) * 1000 * 1000 * 1000 + a0 * 1000 * 1000 + b0 * 1000 + c0); } if ((m - c) >= a) { c0 = c + a;a0 = 0;b0 = b; } else { c0 = m;a0 = a - (m - c);b0 = b; } if (p.count(a0 * 1000 * 1000 + b0 * 1000 + c0) == 0) { p.insert(a0 * 1000 * 1000 + b0 * 1000 + c0); q.push((d + 1) * 1000 * 1000 * 1000 + a0 * 1000 * 1000 + b0 * 1000 + c0); } if ((m - c) >= b) { c0 = c + b;b0 = 0;a0 = a; } else { c0 = m;b0 = b - (m - c);a0 = a; } if (p.count(a0 * 1000 * 1000 + b0 * 1000 + c0) == 0) { p.insert(a0 * 1000 * 1000 + b0 * 1000 + c0); q.push((d + 1) * 1000 * 1000 * 1000 + a0 * 1000 * 1000 + b0 * 1000 + c0); } if ((s - a) >= b) { a0 = a + b;b0 = 0;c0 = c; } else { a0 = s;b0 = b - (s - a);c0 = c; } if (p.count(a0 * 1000 * 1000 + b0 * 1000 + c0) == 0) { p.insert(a0 * 1000 * 1000 + b0 * 1000 + c0); q.push((d + 1) * 1000 * 1000 * 1000 + a0 * 1000 * 1000 + b0 * 1000 + c0); } if ((s - a) >= c) { a0 = a + c;c0 = 0;b0 = b; } else { a0 = s;c0 = c - (s - a);b0 = b; } if (p.count(a0 * 1000 * 1000 + b0 * 1000 + c0) == 0) { p.insert(a0 * 1000 * 1000 + b0 * 1000 + c0); q.push((d + 1) * 1000 * 1000 * 1000 + a0 * 1000 * 1000 + b0 * 1000 + c0); } if ((n - b) >= c) { b0 = b + c;c0 = 0;a0 = a; } else { b0 = n;c0 = c - (n - b);a0 = a; } if (p.count(a0 * 1000 * 1000 + b0 * 1000 + c0) == 0) { p.insert(a0 * 1000 * 1000 + b0 * 1000 + c0); q.push((d + 1) * 1000 * 1000 * 1000 + a0 * 1000 * 1000 + b0 * 1000 + c0); } } if (judge == 0)printf("NO\n"); else printf("%lld\n", judge); }}
HDU 1495 <非常可乐>
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。