暴力

对于一个手动启动的发动机会对全部发动机都造成影响，由于数据只有1e3级别，考虑n2暴力，由于是一个环，t时间,x传到y的关联启动有两个一个t1是abs(x-y)，另外一个t2是n-abs(x-y)，得到关系转移ans[y]=min({ans[y],t1+t,t2+t});最后遍历一遍找到最大值，最后在来一遍把是最大值的放答案里面即可

代码如下

cpp

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define N 10005
int ans[N];

题目内容

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

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

输出

2
0 4

说明

$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$.