题目链接:https://vjudge.net/problem/HDU-1495

题意:有两个空杯(分别是N升和M升)和一罐满的可乐S升,S = N + M,三个容器可以互相倾倒,如果A倒入B,只有两种情况:
(1) A全部倒入B中,B中的升数小于等于B的最大容量。
(2)A部分倒入B中,B已经到达了B的最大容量。
问:有没有可能把S升的可乐平分在任意两个容器中,有的话得出最少操作次数,否则输出“NO”。

思路:bfs,把六种情况都模拟枚举(代码写的比较形象),需要标记出现过的三个容器的容量情况,否则会TLE。


 #include <iostream>
#include <cstring>
#include<vector>
#include<string>
#include <cmath>
#include <map>
#include <queue>
#include <algorithm>
using namespace std; #define inf (1LL << 31) - 1
#define rep(i,j,k) for(int i = (j); i <= (k); i++)
#define rep__(i,j,k) for(int i = (j); i < (k); i++)
#define per(i,j,k) for(int i = (j); i >= (k); i--)
#define per__(i,j,k) for(int i = (j); i > (k); i--) int NL, ML, SL, AVE;
//bool vis[110][110][110]; struct node{ int N, M, S, V; node(int a, int b, int c, int d){
N = a;
M = b;
S = c;
V = d;
} //这里面内嵌的 if表示(1)情况
// else表示(2)情况
void Pour(int f, int s){ if (f == ){
if (s == ){
int t = ML - M;
if (N >= t) N -= t, M = ML; //(1)
else M += N, N = ; //(2)
}
else if (s == ){
int t = SL - S;
if (N >= t) N -= t, S = SL;
else S += N, N = ;
}
}
else if (f == ){
if (s == ){
int t = NL - N;
if (M >= t) M -= t, N = NL;
else N += M, M = ;
}
else if (s == ){
int t = SL - S;
if (M >= t) M -= t, S = SL;
else S += M, M = ;
}
}
else if (f == ){
if (s == ){
int t = NL - N;
if (S >= t) S -= t, N = NL;
else N += S, M = ;
}
else if (s == ){
int t = ML - M;
if (S >= t) S -= t, M = ML;
else M += S, S = ;
}
}
} }; //可以看出,我用了两个方法都可以标记情况
void bfs(){ map<pair<int, int>, bool> mp;//标记三个容器的容量情况,防止出下过的再次出现在队列中
pair<int, int > p(, );
mp[p] = true;
node in(, , SL, );
// vis[in.N][in.M][in.S] = true;
queue<node> que;
que.push(in); while (!que.empty()){ node tmp = que.front();
que.pop(); //六种情况,Pour(x,y) 把X中的倒入y中,应该是很清楚了
rep(i, , ){
node t = tmp; if (i == ) t.Pour(, );
else if (i == ) t.Pour(, );
else if (i == ) t.Pour(, );
else if (i == ) t.Pour(, );
else if (i == ) t.Pour(, );
else if (i == ) t.Pour(, ); //检查有没有出现平分了
int key = ;
if (t.N == AVE) key++;
if (t.M == AVE) key++;
if (t.S == AVE) key++;
//平分了
if (key >= ){
cout << tmp.V + << endl;
return;
} p.first = t.N;
p.second = t.M;
pair<int, int > p(t.N, t.M);
if (!mp[p]/*!vis[t.N][t.M][t.S]*/){
mp[p] = true;
// vis[t.N][t.M][t.S] = true;
que.push(node{ t.N, t.M, t.S, tmp.V + });
}
}
} cout << "NO" << endl;
} int main(){ ios::sync_with_stdio(false);
cin.tie(); while (cin >> SL >> NL >> ML){ memset(vis, , sizeof(vis)); if (NL == && ML == && SL == ) break;
AVE = SL / ;
if (SL & ){
cout << "NO" << endl;
continue;
}
bfs();
} return ;
}

最新文章

  1. svn 合并分支
  2. js string 转 int Number()
  3. .NET 可空值类型
  4. sqlserver 中server 函数GETDATE(),DEFAULT用法
  5. 三层架构和MVC模式
  6. iOS开发之 在release版本禁止输出NSLog内容
  7. javaNIO学习
  8. 【策略】UVa 278 - Chess
  9. FreeMarker-TemplateLoader
  10. sql查询第二大的记录(转)
  11. 「luogu2569」[ZJOI2006] 书架
  12. bitset用法小结
  13. SQL中IF和CASE语句
  14. C#Workbooks 对象的 Open 方法参数说明
  15. lenet-5,Alexnet详解以及tensorflow代码实现
  16. OSI七层模型与TCP/IP四层模型
  17. 数字&amp;字符串
  18. 理解proc目录与linux进程、ps命令、netstat命令的关系
  19. 安装sqlite3.8的方法
  20. a new way of thinking about a problem

热门文章

  1. SICP 关于递归迭代的重新理解以及尾递归的引入...
  2. 随机森林分类器(Random Forest)
  3. 规则“Microsoft Visual Studio 2008 的早期版本”失败。此计算机上安装了 Microsoft Visual Studio 2008 的早期版本。请在安装 SQL Server 2008 前将 Microsoft Visual Studio 2008 升级到 SP1。
  4. Oracle 存储过程创建及调用
  5. Sql 2017 安装到sql_shared_mrconfigaction-install-confignonrc-cpu64卡住不动问题
  6. C#跳转语句
  7. uwp汉堡菜单的实现
  8. DLL中类的显式链接(用虚函数进行显式链接)
  9. 关于Qt 5-MSVC 2015 64位在 win7 64位系统debug程序崩溃的问题
  10. Qt 之 样式表的使用——样式选择器(上下篇,很详细)