题目链接http://acm.hdu.edu.cn/showproblem.php?pid1495分析这道题属于倒水问题分为两种情况一个杯子倒满或者一个杯子倒空用优先队列存储各种状态按照操作次数从小到大排小的先出队列用bfs求最少的操作次数我参考的是刘汝佳的“倒水问题”与这道题思想一致结束条件不同而已。#includeiostream #includecstdio #includecstring #includequeue using namespace std; const int N 100 10; int cup[3],vis[N][N]; struct Node { int v[3],step; bool operator (const Node b) const { return step b.step; } }; bool bfs(int n,int m,int s) { cup[0] n,cup[1] m,cup[2] s; memset(vis,0,sizeof(vis)); priority_queueNode q; Node start; start.v[0] 0,start.v[1] 0,start.v[2] cup[2],start.step 0; q.push(start); vis[0][0] 1; while(!q.empty()) { Node u q.top();q.pop(); for(int i 0; i 3; i) for(int j 0; j 3; j)//结构体当中用数组存储水量方便循环 if(i ! j) { if(u.v[i] 0 || u.v[j] cup[j]) continue;//如果要倒的杯子是空的或者要装的杯子是满的 int amount min(cup[j],u.v[i] u.v[j]) - u.v[j];//倒满或倒空 Node u2; memcpy(u2,u,sizeof(u)); u2.v[i] - amount; u2.v[j] amount; u2.step 1; if(!vis[u2.v[0]][u2.v[1]]) {//因为总水量固定只需两个杯子的水量就可以确定一种状态 vis[u2.v[0]][u2.v[1]] 1; if((u2.v[0] s / 2 || u2.v[1] s / 2) u2.v[2] s / 2) {//结束条件为出现水量平分的状态 printf(%d\n,u2.step); return true; } q.push(u2); } } } return false; } int main() { int s,n,m; while(scanf(%d%d%d,s,n,m) s n m) { if(s % 2) printf(NO\n); else if(!bfs(n,m,s)) printf(NO\n);; } return 0; }