BOJ 1797 균형잡힌 줄서기

* BOJ 1797 균형잡힌 줄서기

[분류 - 정렬, 그리디]

1. 브루트포스로 계산하기에는 O(N^2)은 시간적으로 부담이되기에 일단 x축을 기준으로 정렬한다.

2. x좌표가 작은 값에서 큰 값으로 순회를 시작하는데, 여자면 -1을 할당하고 남자면 1을 할당하여 누적합을 구한다. 이 때 순회하다가 이전에 나왔던 누적합(bef)이 존재한다면 현재와 bef를 비교하여 x좌표가 얼마나 차이가 있는지 계산한다. 이 값 중에 가장 큰 값을 출력해주면 된다.

※ 이 때 누적합이 최초로 등장한 값만 저장해주면 된다. 문제에서 요구하는 것은 x 간격이 가장 큰 것을 원하므로 임의의 누적합이 어디서 최초로 등장했는지를 저장해두고 나중에 다시 이 누적합이 나오면 그것이 곧 최대 간격의 후보를 의미한다.

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAX_N = 1e6 + 1, OFF = 1e6;
int main() {
    pair<int, int> pos[MAX_N];
    int N, i, d[2 * MAX_N], c = 0, ans = 0;
    scanf("%d", &N);
    for (i = 1; i <= N; i++)
        scanf("%d%d", &pos[i].second, &pos[i].first);
    memset(d, -1, sizeof d);
    sort(pos + 1, pos + 1 + N);
    d[OFF] = 0;
    for (i = 1; i <= N; i++) {
        c += pos[i].second ? 1 : -1;
        if (d[c + OFF] != -1)
            ans = max(ans, pos[i].first - pos[d[c + OFF] + 1].first);
        else d[c + OFF] = i;
    }
    printf("%d", ans);
    return 0;
}