3701: 最佳位置(第六轮03)
题目描述
牛牛最近在研究一个问题，他将其称之为“最佳位置”问题。
有n个座位从左到右排成一行，相邻之间两两距离为1 ，编号从1到n。
会有m个人按顺序进来，选择一个座位坐下，新来的人会计算每个位置， 离最近 的已被坐的座位的距离。新来的人会选择距离最大的座位坐下， 如果有多个，他 会选择编号最小的。如果场上都是空位置，来的人会选择坐在位置 1 。
如xoooxoxx, 离被坐的座位的距离就分别为01210100 ， 如果这时候新来一个人， 会选择坐在位置 3 ，变成xoxoxoxx 。
当然，这些人也会离开，而空出当前的位置。
牛牛现在拿到了一张进入和离开的顺序表，他想知道每个人落座时，会选择什么 位置。
输入
第一行输入两个整数n, m，表示座位数目和人的数目。
随后2m行，每行一个整数ai ，如果是第一次出现，表示编号为ai 的人进来；如果 是第二次出现，表示编号为ai 的人离开， 并空出了座位。保证每个人只会进出各
一次。
数据保证每个人只会进来1次，离开1次。
输出
输出m行，每行1个整数，第i行表示编号为i的人选择的座位。
样例输入 复制
9 4
1
2
3
1
4
2
3
4样例输出 复制
1
9
5
1提示
【样例 1 说明】
在座位都没有人时，视所有座位离有人坐过的座位的距离为无穷大。所以一开始 距离一样，会选择坐编号最小的 1 号座位。
在前两人坐了 1,9 之后，距离分别为 012343210 ， 故会选择 5 号座位。
4 进来时，距离情况为 432101210 ，故选择 1 号座位。
【数据范围】
对于 30%的数据有n ≤ 100, m ≤ 100。
对于 60%的数据有1 ≤ n ≤ 10^6 。
其中 20%的数据第一位来的人最后才走，
另有 20%的数据前两位来的人最后才走。˙
对于 100%的数据有1 ≤ m ≤ n ≤ 10^9, 1 ≤ m ≤ 3 ⋅ 10^5 。
注意：题目不保证进入的人按编号顺序进入。 CD 的大数据下载链接：
链接： https://pan.baidu.com/s/1zupTECKeGEpNM-9tQ4TzlQ 提取码： NOIP
或者从这里提取：