由于自己感觉自己讲算法讲的不是那么．．．．．．清晰明了 ㄟ( ▔, ▔ )ㄏ
所以还是分析题吧．．．．．．
这道题．．．．．．反正绕了我很久
比较难过，感觉太麻烦，有很多种可能性，比较烦 ╮（╯＿╰）╭
也是一度放弃过，但是最后静下心来分析．．．．．．
发现其实只要思路清晰就 No Problem ～(￣▽￣～)(～￣▽￣)～
话不多说！来人！上题！
题目 :喝可乐!
夏天到了,没有什么比喝冰可乐更爽的事情了。同样的,和最喜欢的人一起
分享可乐也是一件很快乐的事。现在你买了一瓶 S 毫升的可乐,并且你手边
有两个容量为 N 毫升和 M 毫升的杯子(M + N = S),若你想把这瓶可乐完
美的平分为两份,但无论是可乐瓶还是两个杯子都没有刻度,该怎么办呢?
输入
输入的数据有多组,每组数据在一行内有以空格作为分隔符的三个非负整数
S, N 和 M。若 S, N, M 均为 0,表示输入结束,该组数据 不输出任何内容 。
输出
对于每组数据,若可以平分,则在一行内输出最少需要倒的次数,若不能平
分,则在一行内输出 NO。
样例输入
7 4 3
4 1 3
0 0 0
样例输出
NO
3
不管是深搜算法还是广搜算法，列出所有可能性，都是必须的！！！ (｡･∀･)ﾉﾞ
这道题也是难在了这里！
那么让我们先来分析一下：
1.求的是最少次数，也就是最值，那么必定是广搜算法
2.奇数当然不可以，三个瓶子都说了是整数，奇数平分就成小数了，所以奇数可以直接pass (ﾟДﾟ*)ﾉ
3.开始列可能性：
s 可以倒给m s-m
m 也可以倒给s m-s
s 可以倒给 n s-n
n 也可以倒给 s n-s
ｍ可以倒给n m-n
n也可以倒给 m n-m
你以为这就完了？ <(￣︶￣)>
还有条件：
s 倒给 ｍ 的时候．．．．．．
是不是必须保证，ｓ里面有可乐，而ｍ里面装的下可乐？
那么设ｓ瓶里可乐剩余量为 s1 ,m 瓶里可乐剩余量为 m1
是不是条件就是 s1 > 0 ，m1 < m
其它５种情况也是如此
你以为 这就完了？ ( ﹁ ﹁ ) ~→
在满足 s1 > 0 ，m1 < m 可以从 s 瓶往 m瓶里倒的时候
是倒多少呢？
全部倒，直到 m 瓶满了为止？
那你怎么知道 s 瓶里剩的可乐够将 m 瓶倒满呢？
把 s 瓶倒完了就行了？
那万一溢了怎么办？这是机器．．．．．．不会人工帮你叫停
不管了，倒就行了？
那怎么标记这次倒完后的值？怎么知道下次应该怎么倒？
醒醒吧．．．．．．分析一下 (￣_,￣ )
不要怕麻烦，分情况
判断一下呗
还是 s 瓶给 m 瓶里倒：
－如果 s 瓶里的 剩余量 s1 要比 m瓶里 空余量 (m - m1) 多 的话
那么说明不能将 s1 全倒，因为会溢出来
将 m 倒满就行了, s1 剩着就剩着呗
那么设s2,m2是倒完后的状态 ，那么就是 s2 = s1 - ( m - m1 ) ; m2 = m;
－那么如果反过来呢？剩余量 比 空余量 少
那么就说明 s 瓶可以倒完，m 瓶装不满就装不满呗
那么就是 ：s2 = 0 ; m2 = m1 + s1 ;
你以为这就完了？ (☄⊙ω⊙)☄
好吧，没错
这次是真的完了 ʅ（´◔౪◔）ʃ
看上去只有６种倒的情况
可是再加上分析．．．．．．足足．．．１２种啊 o(╥﹏╥)o
但是呢 只要耐心分析出来一种
其他的１１种，直接复制粘贴再改下字母数字就好了啦 =└(┐卍o)卍
敲黑板 ヽ(￣ω￣(￣ω￣〃)ゝ
重点来了：
这道题怕就怕你在不愿意静下心去分析那第１种可能性
导致后面１１种没有可以复制粘贴的东西
嘿嘿嘿，我开始，就是不愿意去分析第一个的那种人 ╮（╯＿╰）╭
好啦，贴代码．．．．．．还不太懂的童鞋可以对照代码再研究
但是一定要自己顺一遍过程哦 ︿(￣︶￣)︿
#include<stdio.h>
struct node //定义结构体，里面是三个瓶子还有倒的次数
{
int s;
int m;
int n;
int step;
};
int main()
{
struct node q[100000]; //结构体数组．没有必要这么大，可以自己修改
int m,n,s,head,tail,s1,m1,n1,f;
while(1)
{
scanf("%d%d%d",&s,&m,&n); //输入s,m,n
if(s==0 && m==0 && n==0)
break;
if(s%2!=0) //奇数肯定不可以，都是整数的瓶子，平分不了
{
printf("NO\n");
continue;
}
int a[101][101][101]={0}; //标记状态是否已经有过的数组
head=0;
tail=1;
f=0;
q[head].s=s; //初始的状态
q[head].m=0;
q[head].n=0;
q[head].step=0;
a[s][0][0]=1; //初始状态标记
while(head<tail)
{
s1=q[head].s;
m1=q[head].m;
n1=q[head].n;
if( (s1==(s/2) && m1==(s/2) ) || (s1==(s/2) && n1==(s/2) ) || ( m1==(s/2) && n1==(s/2) ) ) //判断结束的条件
{
printf("%d\n",q[head].step);
f=1;
break;
} //开始喽
if(s1>0 && m1<m) //s-m
{
if(s1>(m-m1))
{
q[tail].s=s1-m+m1;
q[tail].m=m;
}
else
{
q[tail].s=0;
q[tail].m=m1+s1;
}
q[tail].n=n1;
if(a[q[tail].s][q[tail].m][q[tail].n]==0)
{
q[tail].step=q[head].step+1;
a[q[tail].s][q[tail].m][q[tail].n]=1;
tail++;
}
}
if(s1>0 && n1<n) //s-n
{
if(s1>(n-n1))
{
q[tail].s=s1-n+n1;
q[tail].n=n;
}
else
{
q[tail].s=0;
q[tail].n=n1+s1;
}
q[tail].m=m1;
if(a[q[tail].s][q[tail].m][q[tail].n]==0)
{
q[tail].step=q[head].step+1;
a[q[tail].s][q[tail].m][q[tail].n]=1;
tail++;
}
}
if(s1<s && m1>0) //m-s
{
if(m1>(s-s1))
{
q[tail].m=m1-(s-s1);
q[tail].s=s;
}
else
{
q[tail].m=0;
q[tail].s=m1+s1;
}
q[tail].n=n1;
if(a[q[tail].s][q[tail].m][q[tail].n]==0)
{
q[tail].step=q[head].step+1;
a[q[tail].s][q[tail].m][q[tail].n]=1;
tail++;
}
}
if(s1<s && n1>0) //n-s
{
if(n1>(s-s1))
{
q[tail].n=n1-(s-s1);
q[tail].s=s;
}
else
{
q[tail].n=0;
q[tail].s=n1+s1;
}
q[tail].m=m1;
if(a[q[tail].s][q[tail].m][q[tail].n]==0)
{
q[tail].step=q[head].step+1;
a[q[tail].s][q[tail].m][q[tail].n]=1;
tail++;
}
}
if(m1>0 && n1<n) //m-n
{
if(m1>(n-n1))
{
q[tail].m=m1-(n-n1);
q[tail].n=n;
}
else
{
q[tail].m=0;
q[tail].n=n1+m1;
}
q[tail].s=s1;
if(a[q[tail].s][q[tail].m][q[tail].n]==0)
{
q[tail].step=q[head].step+1;
a[q[tail].s][q[tail].m][q[tail].n]=1;
tail++;
}
}
if(n1>0 && m1<m) //n-m
{
if(n1>(m-m1))
{
q[tail].n=n1-(m-m1);
q[tail].m=m;
}
else
{
q[tail].n=0;
q[tail].m=m1+n1;
}
q[tail].s=s1;
if(a[q[tail].s][q[tail].m][q[tail].n]==0)
{
q[tail].step=q[head].step+1;
a[q[tail].s][q[tail].m][q[tail].n]=1;
tail++;
}
}
head++;
}
if(f==0)
printf("NO\n");
}
}
我就只分析可能情况了．．．．．．队列什么不太懂的童鞋自己去看一下（其实就是数组，超级简单的） w(ﾟДﾟ)w
ヾ(￣▽￣)ByeBye