M - 非常可乐HDU - 1495
大家一定觉的运动以后喝可乐是一件很惬意的事情，但是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
拉着小妹子一起刷题……莫名debug了好久orz，推荐数论的解法哇，被代码长度还有复杂度深深吸引啊有木有！虽然我不会orz……
emmmmm一开始有些蒙蔽，觉得是个数学题，然贰，大佬说，一眼就是BFS……嘛~记笔记：最少步数求解——BFS！
下面先码BFS的解法（唔，感觉有点像是汉诺塔？？？汉诺塔也迷迷的orz）
先考虑一下有解的情况：这里假设v[3]为三个杯子此刻装有的可乐（假设v[0]>v[1]），那么当v[0]==v[2]&&v[1]==0时，可乐被平分。
if(v[0]==v[2]&&v[0]==0) printf("%d ",t);
无解情况就……队列空了都没找到满足有解的状态（这里队列实现）
每次以三个杯子里的一个杯子为主，拿起来就往其他两个杯子里倒就好了，也没有其他地方可以倒了233333
需要注意的是，这里一直都是把v[i]的倒入v[j]，处理的时候注意倒的量不要超过杯子的容量；
#include<iostream> #include<stdio.h> #include<queue> #include<string.h> using namespace std; struct node { int v[3]; int t; }; int a, b, c; int cup[3]; bool vis[105][105]; void bfs() { node d,e; queue<node>q; d.t = 0; d.v[0] = 0; d.v[1] = 0; d.v[2] = c; q.push(d); vis[0][0] = 1; while (!q.empty()) { d = q.front(); q.pop(); if (d.v[0] == d.v[2] && d.v[1] == 0) { printf("%d ", d.t); return; } for(int i=0;i<3;i++) for (int j = 0; j < 3; j++) { if (d.v[i]==0||d.v[j] == c||i==j) continue; //因为一直都是把i倒到j里，i不为空，j不为满，自己不能倒给自己 int l = min(cup[j], d.v[i] + d.v[j]) - d.v[j]; memcpy(&e, &d, sizeof(d)); e.v[i] -= l; e.v[j] += l; if (!vis[e.v[0]][e.v[1]]) { vis[e.v[0]][e.v[1]] = 1; e.t ++; q.push(e); } } } puts("NO"); } int main() { while (scanf("%d%d%d", &c, &a, &b)!=EOF) { if (a==0 || b==0 || c==0) break; memset(vis, 0, sizeof(vis)); cup[0] = max(a, b); cup[1] = min(a, b); cup[2] = c; bfs(); } return 0; }
数论 ……待续