非常可乐 HDU - 1495 (BFS || 数论)
https://vjudge.net/problem/HDU-1495
倒水问题,开始一看还没读懂题。注意题中所指出的没有刻度这个问题,如果没有刻度的就只能有两种倒发:要么全部倒给另一个杯子,要么把自己的倒完。(这两个可能可以合并为一个算法)
那其实就是搜索问题了,求最优解当然用广搜,两个for循环表示第i个杯子到给第j个杯子。
//非常可乐
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn = 105;
int vis[maxn][maxn][maxn]; //1表示有可乐,0表示没有
int v[3], ans;
struct Node{
int v[3]; //当前3杯水的容量
int steps;
};
Node nextB, curB;
queue<Node> q;
void pour(int from, int to)
{
//很巧妙的倒水算法,行数最少
int tmp = nextB.v[from]+nextB.v[to];
if(tmp >= v[to]) nextB.v[to] = v[to];
else nextB.v[to] = tmp;
nextB.v[from] = tmp-nextB.v[to];
}
void Bfs()
{
if(v[0] % 2 != 0) return; //可行性剪枝
Node t;
t.v[0] = v[0], t.v[1] = 0, t.v[2] = 0, t.steps = 0;
q.push(t);
vis[1][0][0] = 1;
while(!q.empty()){
curB = q.front();
q.pop();
//终点
if((curB.v[0]==curB.v[1]&&curB.v[0]!=0&&curB.v[2]==0)||(curB.v[0]==curB.v[2]&&curB.v[0]!=0&&curB.v[1]==0)||(curB.v[1]==curB.v[2]&&curB.v[1]!=0&&curB.v[0]==0)){
ans = curB.steps;
return;
}
//i给j倒可乐
for(int i = 0; i < 3; i++)
for(int j = 0; j < 3; j++)
if(i!=j){ //不能自己给自己倒
nextB = curB;
pour(i, j); //从i到给j
if(!vis[nextB.v[0]][nextB.v[1]][nextB.v[2]]){
nextB.steps++;
vis[nextB.v[0]][nextB.v[1]][nextB.v[2]]=1;
q.push(nextB);
}
}
}
}
int main()
{
while(scanf("%d%d%d",&v[0],&v[1],&v[2])==3 && (v[0]!=0||v[1]!=0||v[2]!=0)){
while(!q.empty()) q.pop();
memset(vis,0,sizeof(vis));
ans = 1<<30;
Bfs();
if(ans < (1<<30)) printf("%d\n",ans);
else printf("NO\n");
}
return 0;
}
但其实这道题还有一种神仙解法,数论。
转自:https://www.cnblogs.com/ECJTUACM-873284962/p/6750320.html
分析:设两个小瓶子容积分别为a,b,问题转化成通过两个小瓶子的若干次倒进或倒出操作得到(a+b)/2体积的可乐,设两个小瓶子被倒进或倒出x次和y次(这里的x和y是累加后的操作,即x=第一个瓶子倒出的次数-倒进的次数,y=第二个瓶子倒出的次数-倒进的次数),那么问题转化成:
#include <bits/stdc++.h>
using namespace std;
int gcd(int a,int b)
{
return b==0?a:gcd(b,a%b);
}
int main()
{
int a,b,c;
while(cin>>a>>b>>c&&(a&&b&&c))
{
a/=gcd(b,c);
if(a&1)
cout<<"NO"<<endl;
else
cout<<a-1<<endl;
}
return 0;
}
先码住,回头再来研究