1，问题描述
题目描述
流浪地球计划在赤道上均匀部署了 N 个转向发动机，按位置顺序编号为 0~N-1。
- 初始状态下所有的发动机都是未启动状态；
- 发动机启动的方式分为” 手动启动” 和” 关联启动” 两种方式；
- 如果在时刻 1 一个发动机被启动，下一个时刻 2 与之相邻的两个发动机就会被” 关联启动”;
- 如果准备启动某个发动机时，它已经被启动了，则什么都不用做；
- 发动机 0 与发动机 N-1 是相邻的；
地球联合政府准备挑选某些发动机在某些时刻进行 “手动启动”。当然最终所有的发动机都会被启动。
哪些发动机最晚被启动呢？
输入描述
- 第一行两个数字 N 和 E，中间有空格
N 代表部署发动机的总个数，E 代表计划手动启动的发动机总个数
1<N<=1000,1<=E<=1000,E<=N
- 接下来共 E 行，每行都是两个数字 T 和 P，中间有空格
T 代表发动机的手动启动时刻，P 代表此发动机的位置编号。
0<=T<=N.0<=P<N
输出描述
- 第一行一个数字 N，以回车结束
N 代表最后被启动的发动机个数
- 第二行 N 个数字，中间有空格，以回车结束
每个数字代表发动机的位置编号，从小到大排序
示例 1
输入
输出
说明
8 个发动机，时刻 0 启动 2 和 6 号发动机
示例 2
输入：
输出：
说明
8 个发动机，时刻 0 手动启动 0，时刻 1 手动启动 7.
2，初步思考
直接使用 2 个队列进行缓存，
当前应该开启的机器，下一个时间点应该开启的机器
3，代码处理
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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
| import java.util.*;
public class code {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
boolean flag = true;
boolean[] visited = new boolean[1];
int n = 0, e = 0, cnt = 0, minTime = Integer.MAX_VALUE;
List<Integer> temp;
Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
while (in.hasNextLine()) {
String str = in.nextLine();
if (flag) {
String[] split = str.split(" ");
n = Integer.parseInt(split[0]);
visited = new boolean[n];
e = Integer.parseInt(split[1]);
flag = false;
} else {
String[] split = str.split(" ");
int a = Integer.parseInt(split[0]);
int b = Integer.parseInt(split[1]);
minTime = Math.min(minTime, a);
if (map.containsKey(a)) {
temp = map.get(a);
temp.add(b);
} else {
temp = new ArrayList();
temp.add(b);
}
map.put(a, temp);
cnt++;
if (cnt == e) {
break;
}
}
}
if (n == 0 || e == 0) {
System.out.println(0);
}
cnt = minTime;
List<Integer> res = new ArrayList();
Deque<Integer> q1 = new ArrayDeque();
Deque<Integer> q2 = new ArrayDeque();
int machineCnt = 0;
while (machineCnt < n) {
res = new ArrayList();
if (map.containsKey(cnt)) {
temp = map.get(cnt);
} else {
temp = new ArrayList();
}
cnt++;
for (int idx : temp) {
if (!visited[idx]) {
res.add(idx);
machineCnt++;
visited[idx] = true;
addNext(visited, q2, n, idx);
}
}
while (!q1.isEmpty()) {
int idx = q1.poll();
if (!visited[idx]) {
res.add(idx);
machineCnt++;
visited[idx] = true;
addNext(visited, q2, n, idx);
}
}
if (machineCnt == n) {
break;
}
q1 = q2;
q2 = new ArrayDeque();
}
System.out.println(res.size());
Collections.sort(res);
for (int num : res) System.out.print(num + " ");
}
private static void addNext(boolean[] visited, Deque<Integer> q2, int len, int idx) {
if (idx == 0) {
if (!visited[1]) q2.add(1);
if (!visited[len - 1]) q2.add(len - 1);
} else if (idx == len - 1) {
if (!visited[0]) q2.add(0);
if (!visited[len - 2]) q2.add(len - 2);
} else {
if (!visited[idx - 1]) q2.add(idx - 1);
if (!visited[idx + 1]) q2.add(idx + 1);
}
}
}
|