大家一定觉的运动以后喝可乐是一件很惬意的事情，但是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
之前有一道和这个相似的，所以我看到这个题就大胆的写了，不过还是wa了两次，因为细节没注意好，因为状态转移每个都一样所以我就直接复制了，但是复制过程中忘记 改变量 了，结果悲剧了，又一个一个找的错误。
题目思路： 其实这个题和之前那个倒水题目类似，而且这个题目比那个简单，这个题目没有要求记录路径，直接标记加输出就可以了。
细节：
1.六个状态的转移，每个状态后续再跟六个状态：
s->a (1) a会满 (2) a不会满
s->b (1) b会满 (2) b不会满
其余的状态与之类似，在状态转移的时候，注意好，与之无关的变量是不需要改变的，比如说 a->b 那 此时 now.stas=pre.stas，即s的状态与之前相同。
2.结束的条件就是可以平分可乐，但是这里需要注意一下，任意两个瓶子平分都是可以的。我在这里用了 任意两个相等，且另一个为0 ，但是在这里注意 任意 的那两个 必须有值，因为开始 a,b是0，本来就相等。 所以其中一种情况为：
if(pre.staa==pre.stab&&pre.staa&&pre.stab&&pre.stas==0)
return pre.step; 剩下两种肯定也会写了，中间用|| 链接。在这里其实还有另一种写法，就是 staa==s/2&&stab==s/2。 这种代码比较简单，但是由于我笨刚开始写麻烦了。
3. 不要忘记vis数组的初始化，这个数组是用来标记 s,a,b每个的状态是否出现过，而且这个题多组输入所以一定要有初始化！
接下来 ，我就附上AC的代码+注释，还是一样，这种题状态太多，码量太大，要细心：
/*Status
Accepted
Time
46ms
Memory
2880kB
Length
6084
Lang
C++
Submitted
2019-02-26 15:58:23
Shared
Select Code*/
#include <queue>
#include <cstdio>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <iostream>
#include <stack>
#include <algorithm>
#include <vector>
#define MIN(x,y) ((x)<(y)?(x) : (y))
#define MAX(x,y) ((x)>(y)?(x) : (y))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int mod=10007;
const int INF=0x3f3f3f3f;
const int maxn=1e6+5;
bool vis[105][105][105];
int s,a,b;
struct node{
int stas,staa,stab;
int step;
};
int bfs()
{
queue<node>q;
memset(vis,0,sizeof(vis));
node st;
st.staa=0;st.stab=0;st.stas=s;st.step=0;
vis[st.staa][st.stab][st.stas]=true;
q.push(st);
while(!q.empty())
{
node pre=q.front();q.pop();
// printf("%d %d %d\n",pre.staa,pre.stab,pre.stas);
if((pre.staa==s/2&&pre.stab==s/2)||(pre.stas==s/2&&pre.staa==s/2)||(pre.stab==s/2&&pre.stas==s/2)) return pre.step;
if(pre.stas!=0)
{
node now;
if(pre.stas+pre.staa>=a)//s->a the one
{
now.staa=a;now.stab=pre.stab;
now.stas=pre.stas+pre.staa-a;
now.step=pre.step+1;
if(vis[now.staa][now.stab][now.stas]==false)
{
vis[now.staa][now.stab][now.stas]=true;
q.push(now);
}
}
else// s->a the two
{
now.staa=pre.staa+pre.stas;now.stab=pre.stab;
now.stas=0;
now.step=pre.step+1;
if(vis[now.staa][now.stab][now.stas]==false)
{
vis[now.staa][now.stab][now.stas]=true;
q.push(now);
}
}
if(pre.stas+pre.stab>=b) //s->b the one
{
now.staa=pre.staa;now.stab=b;
now.stas=pre.stas+pre.stab-b;
now.step=pre.step+1;
if(vis[now.staa][now.stab][now.stas]==false)
{
vis[now.staa][now.stab][now.stas]=true;
q.push(now);
}
}
else // s->b the two
{
now.staa=pre.staa;now.stab=pre.stab+pre.stas;
now.stas=0;
now.step=pre.step+1;
if(vis[now.staa][now.stab][now.stas]==false)
{
vis[now.staa][now.stab][now.stas]=true;
q.push(now);
}
}
}
if(pre.stab!=0)
{
node now;
if(pre.stab+pre.staa>=a)//b->a the one
{
now.staa=a;now.stab=pre.staa+pre.stab-a;
now.stas=pre.stas;
now.step=pre.step+1;
if(vis[now.staa][now.stab][now.stas]==false)
{
vis[now.staa][now.stab][now.stas]=true;
q.push(now);
}
}
else// b->a the two
{
now.staa=pre.staa+pre.stab;now.stab=0;
now.stas=pre.stas;
now.step=pre.step+1;
if(vis[now.staa][now.stab][now.stas]==false)
{
vis[now.staa][now.stab][now.stas]=true;
q.push(now);
}
}
if(pre.stas+pre.stab>=s) //b->s the one
{
now.staa=pre.staa;
now.stab=pre.stab+pre.stas-s;
now.stas=s;
now.step=pre.step+1;
if(vis[now.staa][now.stab][now.stas]==false)
{
vis[now.staa][now.stab][now.stas]=true;
q.push(now);
}
}
else // b->s the two
{
now.staa=pre.staa;now.stab=0;
now.stas=pre.stas+pre.stab;
now.step=pre.step+1;
if(vis[now.staa][now.stab][now.stas]==false)
{
vis[now.staa][now.stab][now.stas]=true;
q.push(now);
}
}
}
if(pre.staa!=0)
{
node now;
if(pre.stas+pre.staa>=s)//a->s the one
{
now.staa=pre.staa+pre.stas-s;now.stab=pre.stab;
now.stas=s;
now.step=pre.step+1;
if(vis[now.staa][now.stab][now.stas]==false)
{
vis[now.staa][now.stab][now.stas]=true;
q.push(now);
}
}
else// a->s the two
{
now.staa=0;now.stab=pre.stab;
now.stas=pre.stas+pre.staa;
now.step=pre.step+1;
if(vis[now.staa][now.stab][now.stas]==false)
{
vis[now.staa][now.stab][now.stas]=true;
q.push(now);
}
}
if(pre.staa+pre.stab>=b) //a->b the one
{
now.staa=pre.staa+pre.stab-b;
now.stab=b;
now.stas=pre.stas;
now.step=pre.step+1;
if(vis[now.staa][now.stab][now.stas]==false)
{
vis[now.staa][now.stab][now.stas]=true;
q.push(now);
}
}
else // a->b the two
{
now.staa=0;now.stab=pre.staa+pre.stab;
now.stas=pre.stas;
now.step=pre.step+1;
if(vis[now.staa][now.stab][now.stas]==false)
{
vis[now.staa][now.stab][now.stas]=true;
q.push(now);
}
}
}
}
return -1;
}
int main()
{
while(scanf("%d%d%d",&s,&a,&b)&&s&&a&&b)
{
if(s%2==1) printf("NO\n");//奇数一定不平分
else
{
int ans=bfs();
if(ans==-1) printf("NO\n");
else
printf("%d\n",ans);
}
}
return 0;
} 希望大家能一次AC哦，加油。
京公网安备 11010502036488号