非常可乐（bfs）

VJ原题链接

题意：

给你三个杯子:s,a,b 每个杯子的容量vs=va+vb。s杯子里装满了可乐，求使得可乐能够平分成2份的最少倒可乐次数

思路：

直接进行模拟，三个杯子装可乐的状态

1，可以通过一个三维数组来记录，因为每次倾倒有六种选择：s->a,b;a->s,b；b->s,a;当输入的s体积为奇数时，不可能平分，输出NO

2，每次倒可乐时，要确保倾倒容器中有可乐，被倾倒容器里可乐没有满溢才能执行倾倒步骤。并且，每次倾倒的体积应该是 被倾倒容器距满溢需要的体积 和 倾倒容器中包含可乐的体积 中较小的一方。

3.每次倾倒完成后，对当前三个容器中可乐体积的状态进行标记。每当出现一种状态时，若未被标记，则记录倾倒次数+1，否则不计数。初始时，s=s,a=0,b=0应先进行标记。

4.结束条件：当两个容器中可乐体积都等于原来总体积的一般时，结束bfs，输出最少倾倒次数

代码：

#include<stdio.h>
#include<queue>
#include<string.h>
#include<algorithm>
using namespace std;
int vis[110][110][110];//记录当状态是否存在
int v[3];  //三个容器的体积
int ans;   //平分后一份的体积
struct node
{
    int v[3]; //三个容器的状态
    int step; //倾倒次数
};
void bfs()
{
    node p,q; //p:当前状态，q:倾倒后的状态
    memset(vis,0,sizeof(vis));
    queue<node>s;
    p.v[0]=v[0];   //初始化
    p.v[1]=p.v[2]=0;
    p.step=0;
    vis[v[0]][0][0]=1;
    s.push(p);
    while(!s.empty()){
        p=s.front();
        s.pop();
        if((p.v[0]==ans&&p.v[1]==ans)||(p.v[0]==ans&&p.v[2]==ans)||(p.v[1]==ans&&p.v[2]==ans)){
            printf("%d\n",p.step);  //判断结束标志
            return;
        }
        for(int i=0; i<3; i++) //从第i个容器中向第j个容器中倾倒
            if(p.v[i]>0)  //保证第i个容器中有水
            for(int j=0; j<3; j++){
                q=p;     //初始倾倒后的状态等同倾倒前的状态
                if(i==j||q.v[j]==v[j]) //自己倒自己和第j个容器已满溢时跳过
                    continue;
                int t=min(q.v[i],v[j]-q.v[j]); //确定合适的倾倒量，防止溢出
                q.v[i]-=t;
                q.v[j]+=t;
                if(!vis[q.v[0]][q.v[1]][q.v[2]]){
                    vis[q.v[0]][q.v[1]][q.v[2]]=1; //判断q的状态是否达到
                    q.step++;   //记步
                    s.push(q);  
                }
            }
    }
    printf("NO\n");
}
int main()
{
    while(~scanf("%d%d%d",&v[0],&v[1],&v[2])&&v[0]+v[1]+v[2]){
        if(v[0]&1){
            printf("NO\n");  //奇数无需考虑
            continue;;
        }
        ans=v[0]/2;   //判断平分标准
        bfs();
    }
    return 0;
}

有大佬直接用数论搞定，佩服，，没有看懂附上图解一张