AT_abc482_d.Wannabe Zombie
普及-
通过率:0%
时间限制:2.00s
内存限制:1024MB
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
There are N people, numbered 1 to N, standing on a number line.
Person i is standing at coordinate Xi. Here, Xi is even for i=1,2,…,N, and X1<X2<⋯<XN holds.
For each k=1,2,…,N, solve the following problem.
At time 0, person k becomes a zombie. Everyone other than person k remains human.
From time 0 onward, humans and zombies can move freely on the number line at a speed of at most 1 per unit time.
When a zombie and a human are at the same coordinate, that human becomes a zombie.
Find the minimum possible time at which everyone has become a zombie.
It can be proved that the answer is an integer under the constraints of this problem.
有 N 个人,编号为 1 到 N,站在一条数轴上。
第 i 个人位于坐标 Xi 处。其中,对所有 i=1,2,…,N,Xi 均为偶数,且满足 X1<X2<⋯<XN。
对每个 k=1,2,…,N,求解以下问题:
在时刻 0,第 k 个人变为僵尸,其余所有人仍为人类。
从时刻 0 开始,人类与僵尸均可在数轴上以不超过 1 单位长度/单位时间的速度自由移动。
当一个僵尸与一个人类处于同一坐标时,该人类立即变为僵尸。
求所有人全部变为僵尸的最短可能时间。
在本题约束条件下,可以证明答案必为整数。
输入格式
The input is given from Standard Input in the following format:
N
X1 X2 … XN
输入从标准输入中按以下格式给出:
N
X1 X2 … XN
输出格式
Print N lines. The i-th line (1≤i≤N) should contain the answer to the problem for k=i.
输出 N 行。第 i 行(1≤i≤N)应包含该问题在 k=i 时的答案。
输入输出样例
输入#1
5 2 4 10 14 18
输出#1
8 7 6 6 8
输入#2
9 140322306 171833796 356303608 595703832 701965684 798563428 857902324 933683272 971602066
输出#2
415639880 399884135 307649229 280821689 280821689 329120561 358790009 396680483 415639880
说明/提示
Sample 1 Explanation:
For k=1, if person 1 moves in the positive direction of the number line at speed 1 and persons 2,3,4,5 move in the negative direction at speed 1, everyone will have become a zombie by time 8.
For k=2, if each person moves as follows, everyone will have become a zombie by time 7.
- Person 1: Moves in the positive direction at speed 1.
- Person 2: Moves in the positive direction at speed 1 until time 3, and in the negative direction at speed 1 from time 3 onward.
- Person 3: Moves in the negative direction at speed 1 until time 3, and in the positive direction at speed 1 from time 3 onward.
- Person 4: Moves in the negative direction at speed 1.
- Person 5: Moves in the negative direction at speed 1.
Constraints
- 1≤N≤2×105
- 0≤X1<X2<⋯<XN≤109
- Xi is even.
- All input values are integers.
样例 1 解释:
当 k=1 时,若第 1 个人以速度 1 沿数轴正方向移动,而第 2,3,4,5 个人均以速度 1 沿数轴负方向移动,则所有人将在时刻 8 前全部变成僵尸。
当 k=2 时,若每个人按如下方式移动,则所有人将在时刻 7 前全部变成僵尸:
- 第 1 个人:以速度 1 沿正方向移动。
- 第 2 个人:在时刻 3 前以速度 1 沿正方向移动,从时刻 3 起以速度 1 沿负方向移动。
- 第 3 个人:在时刻 3 前以速度 1 沿负方向移动,从时刻 3 起以速度 1 沿正方向移动。
- 第 4 个人:以速度 1 沿负方向移动。
- 第 5 个人:以速度 1 沿负方向移动。
约束条件
- 1≤N≤2×105
- 0≤X1<X2<⋯<XN≤109
- 所有 Xi 均为偶数。
- 所有输入值均为整数。
输入解题思路,AI测评打分。不知道怎么写?