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$。
否则,具体有两种方法:

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

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

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#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;
}
文章目录
  1. 1. 题目链接:
  2. 2. 题意:
  3. 3. 分析:
  4. 4. 代码: