2136번: 개미

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


$O(n\lg n)$

두 개미가 부딪혔을 때, 두 개미 모두 방향이 바뀌므로 서로를 통과해서 진행한다고 봐도 된다.
이런식으로 생각했을 때 모두 떨어지는데까지 걸린 시간은 처음 상황에서 방향이 바뀌지 않는 채로 진행했을 때 가장 오래 머무르는 개미의 이동 시간이다.

개미를 좌표 순으로 a1, a2, a3 ... an 이라고 하자.
모든 개미가 떨어질 때까지 이 개미들의 순서는 바뀔 수 없다. 따라서 처음 <- 방향 개미가 c개 존재했다면
a1, ..., ac 는 왼쪽에서 떨어지며 이 중에 ac가 가장 늦게 떨어진다.
ac+1, ... , an은 오른쪽에서 떨어지며 이 중에 ac+1이 가장 늦게 떨어진다.
처음에 통과한다고 가정해서 풀었을 때 <-방향 개미가 가장 늦게 떨어진다면 ac가 답이고, 아니면 ac+1이 답이다.

#include<cstdio>
#include<algorithm>
using namespace std;
int n, l, a, b, c, pcnt;
pair<int, int> p[100000];
int main() {
    scanf("%d %d", &n, &l);
    for (int i = 1, x; i <= n; i++) {
        scanf("%d", &x);
        if (x<0) c++, a = -x>a ? -x : a;
        else b = l - x > b ? l - x : b;
        p[pcnt++] = { abs(x),i };
    }
    sort(p, p + pcnt);
    if (a>b) printf("%d %d", p[c - 1].second, a);
    else printf("%d %d", p[c].second, b);
    return 0;
}