倒水问题

倒水问题

时间限制：10 sec

空间限制：256 MB

问题描述

邓老师有有 2 个容量分别为 n 单位、m 单位的没有刻度的杯子。初始，它们都是空的。邓老师给了你 t 分钟时间。每一分钟，他都可以做下面 4 件事中的任意一件：

1.用水龙头装满一个杯子。

2.倒空一个杯子。

3.把一个杯子里的水倒到另一个杯子里，直到一个杯子空了或者另一个杯子满了。

4.什么都不做。

邓老师希望最后能获得 d 个单位的水，假设最后两个杯具中水量的总和为 x，那么邓老师的不满意度就为 |d-x|。

你希望邓老师尽可能地满意，于是请你计算邓老师的不满意度最小是多少。

输入格式

一行 4 个整数 n,m,t,d，分别表示两个杯具的容量、时间限制、以及邓老师的期望值。

输格式

一行一个整数，表示邓老师最小的不满意度。

样例输入

样例输

样例解释

你可以在第 1 分钟用水龙头装满任意一个杯子，并在第 2 分钟什么都不做，即可让邓老师的不满意度为 9。

可以证明不存在更优的解。

数据范围

本题共设置 16 个测试点。

对于前 1 个测试点，保证 t=1。对于前 2 个测试点，保证 t<=2。对于前 4 个测试点，保证 t<=4。

对于前 10 个测试点，保证 1<=n,m<=100，1<=t<=100，1<=d<=200。

对于所有的 16 个测试点，保证 1<=n,m<=2,000，1<=t<=200，1<=d<=4,000。

代码

#include <iostream> #include<algorithm> #include<string.h>

#pragma warning(disable:4996) using namespace std;

// ================= 代码实现开始 =================

/* 请在这里定义你需要的全局变量 */ typedef pair<int,int> pii; #define fi first

#define se second

const int N = 2003;

//mind:mind[i][j]表示从初始状态到达状态(i,j)需要的最少步数

//q:用数组模拟的队列

//qh:队头下标

//qt:队尾下标 int mind[N][N]; pii q[N*N];

int qh, qt;

//倒水函数，表示状态p经过第k种策略后倒水的状态

//p:初始状态

//k:策略(在下面详细阐释)

//n,m:两杯子容量

//返回值:最终状态

pii to(pii p, int k, int n, int m)

{

if (k == 0)//策略为倒空杯子一

return pii(0, p.se);

else if (k == 1)//倒空杯子二

return pii(p.fi, 0);

else if (k == 2)//倒满杯子一

return pii(n, p.se);

else if (k == 3)//倒满杯子二

return pii(p.first, m);

//以下两个if暂定，有可能有错误

else if (k == 4)//将杯子二的水向杯子一倒

return pii(min(p.fi + p.se, n), max(0, p.se - (n - p.first)));

else if (k == 5)//将杯子一的水向杯子二倒

return pii(max(0, p.fi - (m - p.se)), min(p.fi + p.se, m));

else//否则什么也不做

return p;

}

// 计算答案的函数

// n, m, t, d：意义均与题目描述一致

// 返回值：即为答案

int getAnswer(int n, int m, int t, int d) {

/* 请在这里设计你的算法 */

//初始化，清空队列，将mind所有位置置为-1表示未访问

memset(mind, -1, sizeof(mind));

qh = qt = 0;

q[++qt] = pii(0, 0);

mind[0][0] = 0;

//进行BFS

while (qh < qt)

{

pii u = q[++qh];//取出队头元素

if (mind[u.fi][u.se] == t)

break;//如果已经进行了t步，那么没必要继续搜索了，退出循环即可

for (int k = 0; k < 6; ++k)//枚举六种策略

{

pii v = to(u, k, n, m);

//以下if的条件暂定，可能有错

if (mind[v.fi][v.se] != -1)//判断目标状态是否曾到达过

continue;

q[++qt] = v;//加入队列

mind[v.fi][v.se] = mind[u.first][u.second]+1;//记录mind

}

}

int ans = d;

for (int i = 0; i <= n; ++i)

for (int j = 0; j <= m; ++j)

if (mind[i][j] != -1)

ans = min(ans,abs(d-i-j));

return ans;

}

// ================= 代码实现结束 =================

int main() {

int n, m, t, d;

scanf("%d%d%d%d", &n, &m, &t, &d);

int ans = getAnswer(n, m, t, d);

printf("%d\n", ans);

return 0;

}