链接: https://vjudge.net/problem/HDU-1495
题意:
大家一定觉的运动以后喝可乐是一件很惬意的事情, 但是 seeyou 却不这么认为. 因为每次当 seeyou 买了可乐以后, 阿牛就要求和 seeyou 一起分享这一瓶可乐, 而且一定要喝的和 seeyou 一样多. 但 seeyou 的手中只有两个杯子, 它们的容量分别是 N 毫升和 M 毫升 可乐的体积为 S (S<101) 毫升 (正好装满一瓶) , 它们三个之间可以相互倒可乐 (都是没有刻度的, 且 S==N+M,101>S>0,N>0,M>0) . 聪明的 ACMER 你们说他们能平分吗? 如果能请输出倒可乐的最少的次数, 如果不能输出 "NO".
思路:
bfs, 每次有六种操作, 挨个尝试, 当两个杯子的值是总水量的一半时返回步数.
否则返回 - 1.
代码:
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- using namespace std;
- typedef long long LL;
- const int MAXN = 100 + 10;
- struct Node
- {
- int s_all, s_used;
- int n_all, n_used;
- int m_all, m_used;
- int step;
- Node(int s1, int s2, int n1, int n2, int m1, int m2, int steps)
- {
- s_all = s1;
- s_used = s2;
- n_all = n1;
- n_used = n2;
- m_all = m1;
- m_used = m2;
- step = steps;
- }
- };
- int s, n, m;
- int vis[MAXN][MAXN][MAXN];
- int Bfs(int s1, int n1, int m1)
- {
- queue<Node> que;
- que.emplace(s, s, n, 0, m, 0, 0);
- vis[s1][0][0] = 1;
- while (!que.empty())
- {
- Node now = que.front();
- if (now.s_used == s / 2 && now.n_used == s / 2)
- return now.step;
- if (now.s_used == s / 2 && now.m_used == s / 2)
- return now.step;
- if (now.n_used == s / 2 && now.m_used == s / 2)
- return now.step;
- que.pop();
- int ns, nn, nm;
- ns = now.s_used - min(now.s_used, now.n_all - now.n_used);
- nn = now.n_used + min(now.s_used, now.n_all - now.n_used);
- nm = now.m_used;
- if (vis[ns][nn][nm] == 0)
- {
- que.emplace(now.s_all, ns, now.n_all, nn, now.m_all, nm, now.step + 1);
- vis[ns][nn][nm] = 1;
- }
- ns = now.s_used - min(now.s_used, now.m_all - now.m_used);
- nn = now.n_used;
- nm = now.m_used + min(now.s_used, now.m_all - now.m_used);
- if (vis[ns][nn][nm] == 0)
- {
- que.emplace(now.s_all, ns, now.n_all, nn, now.m_all, nm, now.step + 1);
- vis[ns][nn][nm] = 1;
- }
- ns = now.s_used + min(now.n_used, now.s_all - now.s_used);
- nn = now.n_used - min(now.n_used, now.s_all - now.s_used);
- nm = now.m_used;
- if (vis[ns][nn][nm] == 0)
- {
- que.emplace(now.s_all, ns, now.n_all, nn, now.m_all, nm, now.step + 1);
- vis[ns][nn][nm] = 1;
- }
- ns = now.s_used;
- nn = now.n_used - min(now.n_used, now.m_all - now.m_used);
- nm = now.m_used + min(now.n_used, now.m_all - now.m_used);
- if (vis[ns][nn][nm] == 0)
- {
- que.emplace(now.s_all, ns, now.n_all, nn, now.m_all, nm, now.step + 1);
- vis[ns][nn][nm] = 1;
- }
- ns = now.s_used + min(now.m_used, now.s_all - now.s_used);
- nn = now.n_used;
- nm = now.m_used - min(now.m_used, now.s_all - now.s_used);
- if (vis[ns][nn][nm] == 0)
- {
- que.emplace(now.s_all, ns, now.n_all, nn, now.m_all, nm, now.step + 1);
- vis[ns][nn][nm] = 1;
- }
- ns = now.s_used;
- nn = now.n_used + min(now.m_used, now.n_all - now.n_used);
- nm = now.m_used - min(now.m_used, now.n_all - now.n_used);
- if (vis[ns][nn][nm] == 0)
- {
- que.emplace(now.s_all, ns, now.n_all, nn, now.m_all, nm, now.step + 1);
- vis[ns][nn][nm] = 1;
- }
- }
- return -1;
- }
- int main()
- {
- while (cin>> s>> n>> m)
- {
- memset(vis, 0, sizeof(vis));
- if (s == 0 && n == 0 && m == 0)
- break;
- if (s % 2 != 0)
- {
- cout << "NO" << endl;
- continue;
- }
- int res = Bfs(s, n, m);
- if (res != -1)
- cout << res << endl;
- else
- cout << "NO" << endl;
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2999133.html