【HDU - 1495】非常可樂
-->非常可樂
Descriptions:
大家一定覺的運動以後喝可樂是一件很惬意的事情,但是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
題目連結:
https://vjudge.net/problem/HDU-1495
因為是平分可樂,那麼s必須是偶數
注意這裡的平分不是指兩個杯子平分,他可以是三個容器的任意兩個容器,這是一個坑(我WA了好多次就是因為這個,真惡心啊)
設三個容器的編号分别為1,2,3,
可樂的六種倒法:1倒2,1倒3,2倒1,2倒3,3倒1,3倒2
模拟這六種道倒法即可
具體的看代碼注釋吧
AC代碼
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#define mod 1000000007
#define eps 1e-6
#define ll long long
#define INF 0x3f3f3f3f
#define MEM(x,y) memset(x,y,sizeof(x))
#define Maxn 10
using namespace std;
int s,n,m;
struct node
{
int k1,k2,k3;//三個容器
int step;//步數
};
node now,net;
int vis[105][105][105];//記錄是否這樣倒過可樂
void bfs()
{
int f=0;
queue<node>q;
now.k1=s,now.k2=0,now.k3=0,now.step=0;
vis[s][0][0]=1;
q.push(now);
while(!q.empty())
{
now=q.front();
q.pop();
if(now.k1==now.k2&&now.k3==0)//k1等于k2且k3等于0,即可樂全被分完
{
f=1;
cout<<now.step<<endl;
break;
}
for(int i=1; i<=6; i++)//六種倒可樂的方法
{
if(i==1)//(1倒入2) 後面的代碼都一樣,就是換了一個容器,思想一樣
{
if(now.k1+now.k2<=n)//如果不能夠裝滿n
{
net.k1=0;
net.k2=now.k1+now.k2;
net.k3=now.k3;
}
else//可以裝滿
{
net.k1=now.k1+now.k2-n;
net.k2=n;
net.k3=now.k3;
}
}
if(i==2)//(1倒入3)
{
if(now.k1+now.k3<=m)//如果不能夠裝滿m
{
net.k1=0;
net.k3=now.k1+now.k3;
net.k2=now.k2;
}
else
{
net.k1=now.k1+now.k3-m;
net.k3=m;
net.k2=now.k2;
}
}
if(i==3)//(2倒入1)
{
if(now.k1+now.k2<=s)//如果不能夠裝滿s
{
net.k1=now.k1+now.k2;
net.k2=0;
net.k3=now.k3;
}
else
{
net.k1=s;
net.k2=now.k1+now.k2-s;
net.k3=now.k3;
}
}
if(i==4)//(2倒入3)
{
if(now.k2+now.k3<=m)//如果不能夠裝滿m
{
net.k2=0;
net.k3=now.k2+now.k3;
net.k1=now.k1;
}
else
{
net.k2=now.k2+now.k3-m;
net.k3=m;
net.k1=now.k1;
}
}
if(i==5)//(3倒入1)
{
if(now.k1+now.k3<=s)//如果不能夠裝滿s
{
net.k1=now.k1+now.k3;
net.k3=0;
net.k2=now.k2;
}
else
{
net.k1=s;
net.k3=now.k1+now.k3-s;
net.k2=now.k2;
}
}
if(i==6)//(3倒入2)
{
if(now.k3+now.k2<=n)//如果不能夠裝滿n
{
net.k3=0;
net.k2=now.k2+now.k3;
net.k1=now.k1;
}
else
{
net.k3=now.k2+now.k3-n;
net.k2=n;
net.k1=now.k1;
}
}
if(!vis[net.k1][net.k2][net.k3])//這樣的裝法沒出現過
{
net.step=now.step+1;
vis[net.k1][net.k2][net.k3]=1;//标記
q.push(net);
}
}
}
if(f==0)
cout<<"NO"<<endl;
}
int main()
{
while(cin>>s>>n>>m,s+n+m)
{
if(n<m)//一直把最大的兩個容器放在k1和k2,這樣最後比較的時候直接比較k1等于k2即可
{
int t=n;
n=m;
m=t;
}
MEM(vis,0);
if(s%2!=0)//奇數肯定不能平分
cout<<"NO"<<endl;
else
bfs();
}
}
posted on 2019-07-08 11:47 Sky丨Star 閱讀(...) 評論(...) 編輯 收藏