暴力

对于一个手动启动的发动机会对全部发动机都造成影响，由于数据只有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];
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,m;
	cin>>n>>m;
	for(int i=0;i<n;i++){
		ans[i]=INT_MAX;
	}
	for(int i=0;i<m;i++){
		int t,x;
		cin>>t>>x;
		for(int j=0;j<n;j++){
			int t1=abs(x-j);
			int t2=n-t1;
			ans[j]=min({ans[j],t1+t,t2+t});
		}
	}
	int mx=0;
	for(int i=0;i<n;i++){
		mx=max(mx,ans[i]);
	}
	vector<int>a;
	for(int i=0;i<n;i++){
	if(ans[i]==mx) a.push_back(i);
	}
	cout<<a.size()<<'\n';
	for(int v:a){
		cout<<v<<' ';
	}
	cout<<'\n';
	return 0;
}

python

def main():
    n, m = map(int, input().split())
    ans = [float('inf')] * n

    for _ in range(m):
        t, x = map(int, input().split())
        for j in range(n):
            t1 = abs(x - j)
            t2 = n - t1
            ans[j] = min(ans[j], t1 + t, t2 + t)

    mx = max(ans)
    a = [i for i in range(n) if ans[i] == mx]

    print(len(a))
    print(' '.join(map(str, a)))

if __name__ == "__main__":
    main()

java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        long[] ans = new long[n];

        for (int i = 0; i < n; i++) {
            ans[i] = Long.MAX_VALUE;
        }

        for (int i = 0; i < m; i++) {
            int t = scanner.nextInt();
            int x = scanner.nextInt();
            for (int j = 0; j < n; j++) {
                long t1 = Math.abs(x - j);
                long t2 = n - t1;
                ans[j] = Math.min(ans[j], Math.min(t1 + t, t2 + t));
            }
        }

        long mx = 0;
        for (int i = 0; i < n; i++) {
            mx = Math.max(mx, ans[i]);
        }

        List<Integer> a = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (ans[i] == mx) {
                a.add(i);
            }
        }

        System.out.println(a.size());
        for (int v : a) {
            System.out.print(v + " ");
        }
        System.out.println();
    }
}

题目内容

流浪地球计划在赤道上均匀部署了$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$.