流浪地球计划(中等)

Posted on In Views:

1，问题描述

题目描述

流浪地球计划在赤道上均匀部署了N个转向发动机，按位置顺序编号为0~N-1。

  1. 初始状态下所有的发动机都是未启动状态;
  2. 发动机启动的方式分为”手动启动”和”关联启动”两种方式;
  3. 如果在时刻1一个发动机被启动，下一个时刻2与之相邻的两个发动机就会被”关联启动”;
  4. 如果准备启动某个发动机时，它已经被启动了，则什么都不用做;
  5. 发动机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

输入

1
2
3
4
8 2
0 2
0 6
123

输出

1
2
3
2
0 4
12

说明

8个发动机，时刻0启动2和6号发动机

示例2

输入：

1
2
3
4
8 2
0 0
1 7
123

输出：

1
2
3
1
4
12

说明

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.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class code {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        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()) { // 注意 while 处理多个 case
            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);
                }
            }

            // 遍历q1和temp
            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);
        }
    }
}