题目描述

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

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

地球联合政府准备挑选某些发动机在某些时刻进行“手动启动”。当然最终所有的发动机都会被启动。哪些发动机最晚被启动呢？

输入描述

第一行两个数字 N 和 E，中间有空格

• N 代表部署发动机的总个数，1 < N ≤ 1000
• E 代表计划手动启动的发动机总个数，1 ≤ E ≤ 1000，E ≤ N

接下来共 E 行，每行都是两个数字 T 和 P，中间有空格

• T 代表发动机的手动启动时刻，0 ≤ T ≤ N
• P 代表次发动机的位置编号，0 ≤ P < N

输出描述

第一行一个数字 N， 以回车结束

• N 代表最后被启动的发动机个数

第二行 N 个数字，中间有空格，以回车结束

• 每个数字代表发动机的位置编号，从小到大排序

用例1

输入

8 2
0 2
0 6

Copy

输出

2
0 4

Copy

说明

8个发动机；

时刻0启动（2,6）;

时刻1启动（1,3,5,7）（其中1,3被2关联启动，5,7被6关联启动）；

时刻2启动（0,4）（其中0被1,7关联启动，4被3,5关联启动）；

至此所有发动机都被启动，最后被启动的有2个，分别是0和4。

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;

void printEngines(vector<int> &engines) {
    int i = 0;
    for (auto e : engines) {
        if (e == 0)
            cout << " [" << i << "] ";
        else
            cout << " [x] ";
        i++;
    }

    cout << endl;
}

int main() {
    int N, E;
    // cout << "enter the engines count and manual start engine count" << endl;
    cin >> N >> E;
    // makesure 1 < N <= 1000 && 1 <= E <= 1000
    if (N < 1 || N > 1000 || E < 1 || E > 1000) {
        cout << "Invalid input" << endl;
        return 0;
    }
    // cout << "engines count:" << N << " manual start engine count:" << E << endl;
    // cout << "enter the time index and manual start engine index" << endl;
    map<int, vector<int>> tpMap;
    int T, P;
    for (size_t i = 0; i < E; i++) {
        cin >> T >> P;
        // makesure 0 <= T <= N && 0 <= P <= N
        if (T < 0 || T > N || P < 0 || P > N) {
            cout << "Invalid input" << endl;
            return 0;
        }
        tpMap[T].push_back(P);
        // cout << "we need manual start " << P << " at tick " << T << endl;
    }

    vector<int> engines(N, 0);

    int started = 0;
    int tick = 0;
    while (started < N) {
        //cout << "tick" << tick << " started" << started  << endl;
        // 先检查是否需要关联启动
        if (tick > 0) {
            if (tpMap.find(tick - 1) != tpMap.end()) {
                vector<int> lastEngines;
                for (auto p : tpMap[tick - 1]) {
                    int left = p - 1 < 0 ? N - 1 : p - 1;
                    int right = p + 1 > N - 1 ? 0 : p + 1;
                    
                    // left
                    if (engines[left] == 0) {
                        engines[left]++;
                        // cout << "auto started " << left << " at tick " << tick << endl;
                        // printEngines(engines);
                        started++;
                        lastEngines.push_back(left);
                        // add left to this tpMap
                        tpMap[tick].push_back(left);
                    }
                    // right
                    if (engines[right] == 0) {
                        engines[right]++;
                        // cout << "auto started " << right << " at tick " << tick << endl;
                        // printEngines(engines);
                        started++;
                        lastEngines.push_back(right);
                        // add right to this tpMap
                        tpMap[tick].push_back(right);
                    }
                }

                if (started == N) {
                    cout << lastEngines.size() << endl;
                    sort(lastEngines.begin(), lastEngines.end());
                    for (auto e : lastEngines) {
                        cout << e << " ";
                    }
                    cout << endl;
                    break;
                }
            }
        }
        // 然后检查当前时刻是否有需要手动启动的
        if (tpMap.find(tick) != tpMap.end()) {
            for (auto p : tpMap[tick]) {
                // already started
                if (engines[p] != 0)
                    continue;
                engines[p]++;
                started++;
                // cout << "manual started " << p << " at tick " << tick  << endl;
                // printEngines(engines);
            }
        }
        tick++;
    }
    return 0；
}