本文主要是介绍Jugs ACM，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
原题大意：
你有两个杯子，A、B；你只有三种操作，（1）清空任何一个杯子 （2）当被子是空的时候可以填满任何一个杯子 （3）将某一杯的水倒到另一杯中（不会溢出计算）直到B杯达到目标数Aim C。
输入的A、B升数有要求，一定需要相邻互质。并且A小于B，且目标数Aim C要小于B即可。
题目好像想象挺容易，手写也好像能解出来，但就是电脑老是犯傻逼。扔HDU的OJ上老是显示超时，我看了一下时间限制也很足够啊：
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
这道题我居然在一个小学课本的趣味题发现的，真的是，现在的小学益智题怕是很多都能改成编程题了，而且改了编程题之后你还不一定解的出来哈哈哈。
题目分析：
其实方法很简单，你们可以试一下下面这个步骤，是一定能得到结果的：
（1）装满A
（2）从A倒B
（3）如果B满了清空
基本以上三个步骤都能找打准确的结果。
这就是经典的“灌水定理”，这里提一下，在下面我会引出这个定理，理论上倒水的步骤是不唯一的，所以我就太在意样例。
然而在无数次交OJ的时候疯狂的WA超时，我终于从样例发现了不对劲。在其他OJ上是可以过的，但在HDU OJ好像并没有被智能处理化：
如果目标数C小于A，必须从A开始倒满。如果目标数C大于A，则必须从B开始倒满。原因是为了寻求最短步骤操作，拿样例来说，3 5 4，如果先倒A，那么你需要八步，而如果先到B，那么你需要六步，所以这道题杭电OJ是默认要求最短步骤了，题目并没有说，所以害我 一股脑热直接从A循环交，就错了。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
const int MAXN=1050;
struct node{int a,b;node(int _a,int _b):a(_a),b(_b){}
};
int A,B,N;
int vis[MAXN][MAXN];
vector<int> path[MAXN][MAXN];
void op(int &a,int &b,int i){switch(i){case 1:{a=A;break;}case 2:{b=B;break;}case 3:{a=0;break;}case 4:{b=0;break;}case 5:{if(a+b>B){a=(a+b)-B;b=B;}else{b+=a;a=0;}break;}case 6:{if(b+a>A){b=(b+a)-A;a=A;}else{a+=b;b=0;}break;}}
}
void op_print(int i){switch(i){case 1:{printf("fill A\n");break;}case 2:{printf("fill B\n");break;}case 3:{printf("empty A\n");break;}case 4:{printf("empty B\n");break;}case 5:{printf("pour A B\n");break;}case 6:{printf("pour B A\n");break;}}
}
void bfs(){memset(vis,-1,sizeof(vis));for(int i=0;i<A;i++){for(int j=0;j<B;j++){path[i][j].clear();}}queue<node> que;que.push(node(0,0));vis[0][0]=0;while(!que.empty()){node tmp=que.front();que.pop();int ta=tmp.a;int tb=tmp.b;if(tb==N){for(int i=0;i<path[ta][tb].size();i++){op_print(path[ta][tb][i]);}printf("success\n");return;}for(int i=1;i<=6;i++){int ta=tmp.a;int tb=tmp.b;op(ta,tb,i);if(vis[ta][tb]==-1){vis[ta][tb]=vis[tmp.a][tmp.b]+1;for(int j=0;j<vis[tmp.a][tmp.b];j++){path[ta][tb].push_back(path[tmp.a][tmp.b][j]);}path[ta][tb].push_back(i);que.push(node(ta,tb));}}}
}
int main(void){while(~scanf("%d%d%d",&A,&B,&N)){bfs();}return 0;
}
这篇关于Jugs ACM的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
