Problem Q
Time Limit : 2000/1000ms (Java/Other) Memory Limit :32768/32768K (Java/Other)
Total Submission(s) : 4 Accepted Submission(s) : 1
Problem Description
大家一定觉的运动以后喝可乐是一件很惬意的事情,但是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
算法分析:
一开始上来这题是有点蒙b的,随便在纸上写了几个,第一个规律s为奇数肯定不行,开始以为能找到规律。
Eg:
4 1 3
3 3/1
4 2 2
1 2/2
8 1 7
7 7/1
8 2 6
3 6/2
12 102
5 10/2
还自我感觉找到了,上面就是m/n(假设m>n),但是发现如果m,n都为奇数且除不尽,eg 12 57 倒了几下,没倒出来,就觉得没有,按照这个思想提交上去,果然答案错误,发现 12 5 7 最少步数为11,还有一种特殊情况 12 4 8 是 NO 觉得找不到规律的NO,只能用bfs了。
bfs其实有六种状态(就是各个杯子之间互相到),倒的时候也分两种情况:倒满和倒不满。具体看代码(最后有数学做法)
代码实现:
#include<bits/stdc++.h>
using namespace std;
int vis[100][100][100];
struct v
{int now[3],step; //now表示当前杯子的水的体积
}a,b;
int bfs(int tv[])
{queue<v>q;while(!q.empty()){q.pop();}memset(vis,0,sizeof(vis));//清0工作a.now[0]=tv[0];a.now[1]=0;a.now[2]=0;a.step=0;q.push(a);vis[a.now[0]][a.now[1]][a.now[2]]=1;int i,j;while(!q.empty()){a=q.front();q.pop();for(i=0;i<3;i++)//表示去倒水的瓶子{if(a.now[i]>0)for(j=0;j<3;j++)//表示接受水的瓶子{b=a; //易漏点,注意这里用的循环,六种决策都得有共同前一个状态来得if(i==j) continue; //自己不能给自己倒水if(a.now[i]>=tv[j]-a.now[j])//这里是倒满的情况{b.now[i]-=tv[j]-a.now[j];//倒水的杯子倒出水,注意顺序b.now[j]=tv[j]; //接水的杯子接受水}else //这里即倒不满的情况{b.now[j]+=b.now[i]; //先接水,注意顺序b.now[i]=0; //再倒水}if(!vis[b.now[0]][b.now[1]][b.now[2]]){vis[b.now[0]][b.now[1]][b.now[2]]=1;b.step=a.step+1;if(max(b.now[0],max(b.now[1],b.now[2]))==tv[0]/2&&min(b.now[0],min(b.now[1],b.now[2]))==0){cout<<b.step<<endl;return 0;}q.push(b);}}}}cout<<"NO"<<endl;return 0;
}
int main()
{int tv[3]; //瓶子体容量while(scanf("%d%d%d",&tv[0],&tv[1],&tv[2])&&(tv[1]||tv[2]||tv[0])){if(tv[0]%2!=0) cout<<"NO"<<endl;else if(tv[1]==tv[0]/2||tv[2]==tv[0]/2)cout<<1<<endl;else if(min(tv[1],tv[2])==1)cout<<tv[0]-1<<endl;//上面为剪枝else{bfs(tv);}}return 0;
}
最后觉得肯定有规律,上网一搜,果然有:
代码如下:
#include<bits/stdc++.h>
using namespace std;
int gcd(int x,int y)
{return y?gcd(y,x%y):x;//辗转相除法,最大公倍数
}
int main()
{int s,n,m;while(scanf("%d%d%d",&s,&m,&n),n||m||s){//cout<<gcd(m,n)<<endl;s=s/gcd(m,n);if(s%2==1)//原来是if(s&1)cout<<"NO"<<endl;elsecout<<s-1<<endl;}return 0;
}
还有几个高级写法
这里