2431번: 신호 장애

https://www.acmicpc.net/problem/2431

$O(n\lg n)$

먼저, 반대편 레일로 이동하는데 걸리는 시간이 없으므로 처음 주어진 이동방향은 의미가 없다.

고로 모든 열차가 1차원 좌표계에 있고 좌우로 움직일 수 있다고 생각하자.

오름차순 정렬된 지하철의 위치 a[0...n-1],

오름차순 정렬된 최종 위치 b[0...n-1]이 주어져 있을 때

답은 max(|a[i]-b[i]|) 이다.

최종적으로 가장 왼쪽의 지하철 위치를 x, 간격을 d라 하면

b[0]=x

b[1]=d-x

b[2]=x+d

b[3]=2d-x

...

이에 따라 |a[i]-b[i]| 들은 |x-c[i]| 형태임을 알 수 있고 이들의 최댓값이 이루는 함수는

y=max(|x-min(c[i])|,|x-max(c[i])|) 이다.

x={max(c[i])+min(c[i])}/2일 때 최솟값 y={max(c[i])-min(c[i])}/2을 가진다.

참고로 처음 정렬상태에 따른 정의역 0<=x<=d/2는 잘 생각해보면 고려할 필요가 없다.

#include<cstdio>
#include<algorithm>
using namespace std;
int m, n, a[100000];
double mini = 1e9, maxi = -1e9;
int main() {
    scanf("%d%d", &m, &n);
    for (int i = 0, x; i < n; i++) scanf("%d %*c", a + i);
    sort(a, a + n);
    for (int i = 0; i < n; i++) {
        double t = a[i] - (i + 1) / 2 * 2.0*m / n;
        if (i & 1) t *= -1;
        maxi = max(maxi, t);
        mini = min(mini, t);
    }
    printf("%lf", (maxi - mini) / 2);
    return 0;
}