2016-10-08

HDU 5802 Windows 10【贪心】

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=5802

题意：

给定$p,q$，每次可以上升一个单位，最初可以下降一个单位，但是若上一次下降$x$单位，那么连续的下一次就要下降$2x$个单位，若上一次上升或者停顿，那么连续的下一次就下降一个单位。
问最少上升、停顿、下降的操作数。已知可以上升到无限大，但是只能下降到$0$。
数据范围：$0\le p,q\le 10^9$

分析：

比较容易想到贪心的做法，
若$p \le q$，答案即为$q - p$。
否则，具体有两种方法：

直接贪到最小的比$p$大的，再通过停顿来调整，重新开始，转化为对剩下部分子问题的处理。
直接贪到最大的比$p$小的，再一步步加回来。

我们发现加的过程同样可以起到停顿调整的作用，那么在第$1$种方法中，若在子问题的处理时采用了第$2$种贪心的方法，前面的停顿部分便可以通过加来抵消，相当于在原本停顿的地方上升。
最后注意第二种方法不是不可以减到负数，而是此时负数会自动变成$0$。（被题意坑了好久，看到clarification才明白）

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 30 + 5, oo = 0x3f3f3f3f;
int ans;
int f[maxn];
void init()
{
	for(int i = 1; i <= 30; ++i){
		f[i] = (1 << i) - 1;
	}
}
int q;
void dfs(int pp, int now, int stop)
{
	if(pp == q){
		ans = min(ans, now + stop - 1);
		return;
	}
	int tmp = upper_bound(f + 1, f + 30, pp - q) - f;
	int minus = pp - f[tmp];
	if(minus < 0) minus = 0;
	ans = min(ans, now + tmp + max(q - minus, stop));
	//stop
	dfs(pp - f[tmp - 1], now + tmp - 1, stop + 1); 
}
int main (void)
{
	int T;scanf("%d", &T);
	init();
	while(T--){
		int p; scanf("%d%d", &p, &q);
		if(p <= q){
			printf("%d\n", q - p);
			continue;
		}
		ans = oo;
		dfs(p, 0, 0);
		printf("%d\n", ans);
	}
	return 0;
}