题意
大家一定觉的运动以后喝可乐是一件很惬意的事情，但是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
---------------------------------------------------------我是分割线----------------------------------------------------------------------------------------------------------------------
某童靴的一般思路 (感谢@陌类 提供的代码)
(较麻烦的题解, 好像多数人都这么写~
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#define N 110
using namespace std;
int vis[N][N][N];
int s,n,m;
struct node
{
int n,s,m,step;
};
int cheak(int x,int y,int z)
{
if(x==&&y==z)
return ;
if(y==&&x==z)
return ;
if(z==&&x==y)
return ;
return ;
}
int bfs()
{
queue<node>Q;
node now,next;
now.s=s;
now.n=;
now.m=;
now.step=;
vis[s][][]=;
Q.push(now);
while(Q.size())
{
now=Q.front();
Q.pop();
if(cheak(now.s,now.n,now.m))//检查状态
{
return now.step;
}
for(int i=;i<=;i++)
{
if(now.s!=)
{
if(i==&&now.n!=n)
{
if(now.n+now.s>n)
{
next.n=n;
next.s=now.s-(n-now.n);
}
else
{
next.n=now.n+now.s;
next.s=;
}
next.m=now.m;
next.step=now.step+;
if(!vis[next.s][next.n][next.m])
{
vis[next.s][next.n][next.m]=;
Q.push(next);
}
}
else if(i==&&now.s!=&&now.m!=m)
{
if(now.m+now.s>m)
{
next.m=m;
next.s=now.s-(m-now.m);
}
else
{
next.m=now.m+now.s;
next.s=;
}
next.n=now.n;
next.step=now.step+;
if(!vis[next.s][next.n][next.m])
{
vis[next.s][next.n][next.m]=;
Q.push(next);
}
}
}
if(now.n!=)
{
if(i==&&now.m!=m)
{
if(now.m+now.n>m)
{
next.m=m;
next.n=now.n-(m-now.m);
}
else
{
next.m=now.m+now.n;
next.n=;
}
next.s=now.s;
next.step=now.step+;
if(!vis[next.s][next.n][next.m])
{
vis[next.s][next.n][next.m]=;
Q.push(next);
}
}
else if(i==&&now.n!=&&now.s!=s)
{
if(now.m+now.s>s)
{
next.s=s;
next.n=now.n-(s-now.s);
}
else
{
next.s=now.n+now.s;
next.n=;
}
next.m=now.m;
next.step=now.step+;
if(!vis[next.s][next.n][next.m])
{
vis[next.s][next.n][next.m]=;
Q.push(next);
}
}
}
if(now.m!=)
{
if(i==&&now.m!=&&now.n!=n)
{
if(now.n+now.m>n)
{
next.n=n;
next.m=now.m-(n-now.n);
}
else
{
next.n=now.n+now.m;
next.m=;
}
next.s=now.s;
next.step=now.step+;
if(!vis[next.s][next.n][next.m])
{
vis[next.s][next.n][next.m]=;
Q.push(next);
}
}
else if(i==&&now.m!=&&now.s!=s)
{
if(now.s+now.m>s)
{
next.s=s;
next.m=now.m-(s-now.s);
}
else
{
next.s=now.s+now.m;
next.m=;
}
next.n=now.n;
next.step=now.step+;
if(!vis[next.s][next.n][next.m])
{
vis[next.s][next.n][next.m]=;
Q.push(next);
}
} }
}
}
return -;
}
int main()
{
while(scanf("%d%d%d",&s,&n,&m),s+n+m!=)
{
if(s%!=)
{
printf("NO\n");
}
else
{
memset(vis,,sizeof(vis));
int ans;
ans=bfs();
if(ans>=)
printf("%d\n",ans);
else
printf("NO\n");
}
}
return ;
}
简单点评
在上面的代码, 每次for循环都将枚举六种情况 ,1->2 , 1-》3,2-》3 ，2-》1,3-》1,3-》2 ，并且每种情况又要分为两种来讨论......
重复的部分太多了~
重复的部分太多了~
不够简洁，代码太长长了。
出错误了一不好找啊!
-------------------------------------------------------------------------------------------------------------------------------------我是分割线---------------------------------------------------------------------------------------------------------------------------------------------------------------------------
起先我也是这么做的，后来我想了一个相对简单的优化办法：
进行结构体的嵌套 ,结构体cup 的 a[1]/a[2]/a[3]分别代表这 三个容器 ,其中结构体 cup中 up 代表一个容器的装水上限 ,now 代表现在的水量! 再用 结构体node 将cup和step 封装起来!
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring> //by @山枫叶纷飞
#include<cstdlib>
#include<cmath>
#include<string>
#include<set>
#include<queue>
using namespace std;
typedef long long ll;
double dinf=99999999.9, mm=1e-;
const int N=,inf=0x3f3f3f3f;
int s,n,m;
int vis[N][N][N];
struct cup
{
int up,now;
};
struct node
{
cup a[]; ///进行结构体的嵌套 ,a[1]/a[2]/a[3] 分别表示三个容器
int step;
};
int bfs( )
{
int i,j,k;
queue<node>Q;
node p,q;
p.a[].now=s;p.a[].up=s;
p.a[].now=;p.a[].up=n;
p.a[].now=;p.a[].up=m;
p.step=;
memset(vis,,sizeof(vis));vis[s][][]=;
Q.push(p);
while(Q.size()>)
{
p=Q.front(); ///从队列中取到的现在的状态
Q.pop();
if((p.a[].now==s/&&p.a[].now==s/) || (p.a[].now==s/&&p.a[].now==s/))///判断是否达到预期结果
return p.step;
if((p.a[].now==s/&&p.a[].now==s/))///判断是否达到预期结果(太长了,拆成了两段)
return p.step; for(i=;i<=;i++)
{
for(j=;j<=;j++)
{
if(i==j || p.a[i].now==||p.a[j].now==p.a[j].up)///简易排除
continue; q=p;///初始化,q 代表由p 延伸来的下一状态 int dif=p.a[j].up-p.a[j].now;///表示容器a[j]最多可添加水量
if(p.a[i].now>=dif)///若容器a[j]可被填满水
{
q.a[i].now=p.a[i].now-dif;
q.a[j].now=p.a[j].up;
}
else ///若容器a[j]不能装满水
{
q.a[i].now=;
q.a[j].now=p.a[i].now+p.a[j].now;
}
q.step=p.step+;
if(vis[q.a[].now][q.a[].now][q.a[].now]==)
{
vis[q.a[].now][q.a[].now][q.a[].now]=;
Q.push(q);
}
}
} }
return -;
}
int main()
{
while(scanf("%d%d%d",&s,&n,&m),s+n+m)
{
if(s%!=)///奇数一定无法均分成两份
printf("NO\n");
else
{
int k=bfs();
if(k==-)
printf("NO\n");
else
printf("%d\n",k);
}
} return ;
}
简单点评
两重for 循环，用a[i] 和a[j] 来模拟全部六种情况的倒水过程 ,省了超过100行的代码, 结构体的含义一目了然, 就是结构体名字写起来太长了!
还有要注意的是: { q=p;///初始化,q 代表由p 延伸来的下一状态}这段代码的位置很重要, 每次新的内层for循环都要记得将q重新初始化, 不然会造成意料之外的错误! 当时debug 到了 "debug人在天涯"!
---------------------------------------------------------我是分割线----------------------------------------------------------------------------------------------------------------------
其他思路
这个题目用数论也是可以做的! 近似玄学，，，感兴趣的话自行百度！