我的博客

hduoj 6669 Game - 百度之星 2019

目录
  1. 题目描述
    1. Problem Description
    2. Input
    3. Output
    4. Sample Input
    5. Sample Output
    6. 样例描述
    7. Source
  2. 解答
    1. 第一阶段 选定初始位置
    2. 第二阶段 移动

题目描述

Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 32768/32768 K (Java/Others)

Problem Description

度度熊在玩一个好玩的游戏。
游戏的主人公站在一根数轴上,他可以在数轴上任意移动,对于每次移动,他可以选择往左或往右走一格或两格。
现在他要依次完成 n 个任务,对于任务 i,只要他处于区间 [ai,bi] 上,就算完成了任务。
度度熊想知道,为了完成所有的任务,最少需要移动多少次?
度度熊可以任意选择初始位置。

Input

第一行一个整数 T (1≤T≤10) 表示数据组数。
对于每组数据,第一行一个整数 n (1≤n≤1000) 表示任务数。
接下来 n 行,第 i 行两个整数 ai,bi (1≤ai≤bi≤1000000) 表示任务对应的区间。

Output

对于每组数据,一行一个整数表示答案。

Sample Input

1
2
3
4
1
2
1 10
20 30

Sample Output

1
5

样例描述

选取10为起点,经过的轨迹为10-12-14-16-18-20。

Source

2019 年百度之星·程序设计大赛 - 初赛一

解答

贪心算法。从当前情况出发,选择最少的移动次数。

算法分为两个阶段。

  1. 选定初始位置
  2. 移动

我们算法流程是从头到尾遍历。

第一阶段 选定初始位置

刚开始我们处于第一阶段 选定初始位置,这一阶段需要维护两个变量,保存上一个区间的范围,用于判断当前区间和上一区间是否有交集,如果没有则选定初始位置,进入第二步,如果有用两区间的交集更新区间变量。

第一个区间时,我们没必要确定起始点的具体位置(除非第一个区间长度为 0),起始点只要在第一个区间内任意位置,都是局部最优的,因为不需要任何移动。所有,第一个区间时,移动的步数一定是 0。所以如果区间数量为 0,我们就直接输出 0。

如果后面还有区间:

  1. 如果后面的区间和第一个区间有相交的部分,那么,移动步数仍然为 0。因为只要把起始点选在两区间交集上就可以了。
  2. 如果后面区间和第一个区间无相交部分。那么此时需要选择初始位置,而且局部最优的初始位置是唯一的,就是第一个区间更靠近第二个区间的端点。这样不需要移动就可以满足第一个区间。然后进入第二阶段移动

第二阶段 移动

这个阶段需要维护一个变量,表示当前的位置。

移动的基本策略就是移动到目标区间距离当前位置最近的边缘。

但是这里有一个问题,就是我们一次可以移动两个或者一格,所以存在一种情况,我们可以选择停留在区间的端点上或者端点的下一个格子,而使用相同的移动次数。具体选择哪种要看下一个区间的位置离哪一种更近。如果遇到这种选择,可以使用一个变量记录下来,到下一个区间再做决定。

代码

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <cstdio>

int main() {
int T;
scanf("%d", &T);
while (T--) {
int n;
scanf("%d", &n);
int a, b;
if (n == 1) {
scanf("%d%d", &a, &b);
printf("0\n");
}
else {
scanf("%d%d", &a, &b);
int c, d, i = 1, s = 0, last_p = -1;
int flag = 0;
while (i < n) {
i++;
scanf("%d%d", &c, &d);
if (b <= c) {
last_p = c;
s += (c - b + 1) >> 1;
if ((c - b) % 2 != 0 && c + 1 <= d) {
flag = 1;
}
break;
}
else if (a >= d){
last_p = d;
s += (a - d + 1) >> 1;
if (a - d % 2 != 0 && d - 1 >= c) {
flag = -1;
}
break;
}
else {
if (c > a) {
a = c;
}
if (d < b) {
b = d;
}
}

}
//printf("flag = %d\t", flag);
//printf("to %d\n", last_p);
while (i < n) {
scanf("%d%d", &a, &b);
if (last_p < a) {
if (flag == 1) {
last_p += 1;
//printf("fix to %d\n", last_p);
}
s += (a - last_p + 1) >> 1;
if ((a - last_p) % 2 != 0 && a + 1 <= b) {
flag = 1;
}
else {
flag = 0;
}

last_p = a;
}
else if (last_p > b) {
if (flag == -1) {
last_p -= 1;
//printf("fix to %d\n", last_p);
}
s += (last_p - b + 1) >> 1;
if ((last_p - b) % 2 != 0 && b - 1 >= a) {
flag = -1;
}
else {
flag = 0;
}
last_p = b;
}
//printf("flag = %d\t", flag);
//printf("to %d\n", last_p);
i++;
}
printf("%d\n", s);
}
}
}

评论无需登录,可以匿名,欢迎评论!