[BOJ] 31965 - 회의 장소

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

BOJ - 회의 장소

문제 유형: 수학, 이진 탐색, 누적 합

문제 난이도: Gold I

시간 제한: 1초

메모리 제한: 1024MB

 

문제

KOI 마을에는 N개의 집이 수직선 위에 지어져 있다. 각 집에는 사람들이 한 명씩 살고 있다. 사람들이 살고 있는 집의 좌표를 작은 순서대로 차례대로 나열했을 때, i (1≤i≤N)번째 집의 좌표는 Xi (Xi>0)이다. 마을에 일이 생기면, 마을 사람들은 회의 세트를 통해서 일을 해결한다. 회의 세트는 마을 사람들 전체가 참여할 수도 있고, 일부만 참여할 수도 있다. 회의 세트는 회의들로 구성된다. 회의는 회의 세트의 모든 참여자들이 그중 한 사람의 집에서 모이는 방식으로 진행된다. 회의 세트에서는 모든 참여자들의 집에서 각각 한 번씩 회의를 한다. 즉, 회의 세트에 K명의 마을 사람들이 참여한다면, 회의 세트에서는 K번의 회의를 하게 된다. 회의 한 번에 필요한 비용은 회의에 참여하는 각 사람이 자신의 집에서 회의 장소인 집까지 이동하는 거리의 합이다. 회의 세트의 피로도는 각 회의를 할 때 모이는 집의 순서에 따라 달라진다. 회의 세트의 피로도는 모이는 순서에서 인접한 두 집의 회의 비용 차이의 합으로 정의한다.

예를 들어, 좌표 1, 3, 10, 11, 15에 지어진 집에 사람들이 살고 있고, 3, 10, 11번 집에 사는 사람들이 회의 세트에 참여한다고 하자. 이때, 좌표가 3인 집에 모이기 위한 비용은 |3−3|+|3−10|+|3−11|=15이고, 좌표가 10인 집에 모이기 위한 비용은 |10−3|+|10−10|+|10−11|=8, 좌표가 11인 집에 모이기 위한 비용은 |11−3|+|11−10|+|11−11|=9이다. 이때, 회의를 위해 모이는 집의 좌표 순서가 3−10−11일 경우, 회의 세트의 피로도는 |15−8|+|8−9|=8이다. 반면, 모이는 집의 좌표 순서가 3−11−10일 경우, 피로도는 |15−9|+|9−8|=7이다. 이 순서로 모일 때, 회의 세트의 피로도가 최소이다.

단, 회의 세트에 참여하는 사람이 1명 이하일 경우, 0이 피로도이다.

KOI 마을에서는 총 Q번 회의 세트가 열릴 것이다. i번째 회의 세트는 집의 좌표가 Li이하인 집에 사는 사람들이 참여한다. 각 회의 세트의 최소 피로도를 구하는 프로그램을 작성하라.

 

입력

첫 번째 줄에 N과 Q가 공백으로 구분되어 주어진다.

두 번째 줄에는 마을에 사람이 살고 있는 집들의 좌표 Xi가 증가하는 순서대로 주어진다.

다음 Q개의 줄에, 회의 세트에 대한 정보가 주어진다. i (1≤i≤Q)번째 줄에는 i번째 회의 세트에 대한 정보 Li와 Ri가 공백으로 구분되어 주어진다.

 

출력

Q개의 줄을 출력한다. i (1≤i≤Q)번째 줄에는 i번째 회의 세트의 최소 피로도의 값을 출력한다.

 

풀이

각 쿼리별로 범위를 찾기 위해 이진 탐색이 사용되므로, 첫 비용으로만 q log n이다.

즉, 최소값을 O(1)에 찾아야 한다.

어떻게 이렇게 찾을 수 있을까?

 

피로도 계산의 예제를 보자. 항상 피로도의 최대 값에서 최소 값을 뺀 값이 정답임을 알 수 있다.

그렇다면, 무엇이 최대 값이고, 무엇이 최소 값일까?

범위의 양 끝 값이 항상 최대일 수 밖에 없음을 알 수 있다.

그리고, 중앙의 위치가 항상 최소일 수 밖에 없다.

 

구간 합을 구해서, prefix_sum[i+1] = a[i] + prefix_sum[i]로 구성한다.

0-based기준, 한 위치 i와 구간 [l, r]의 피로도는 다음과 같다:

• i보다 왼쪽 사람들의 피로도: (i - l) * x[i] - (prefix_sum[i] - prefix_sum[l])
• i보다 오른쪽 사람들의 피로도: (prefix_sum[r+1] - prefix_sum[i+1]) - x[i] * (r - i)

쿼리 L, R이 주어졌을 때,

이진탐색을 통해 l, r범위를 구했다고 해보자. l은 a에서 L을 lower_bound로 찾은 것, r은 a에서 R을 upper_bound로 찾아서 1인덱스를 뺀 위치이다.

정답은 max(cost_l, cost_r) - cost_mid이다.

 

 

코드

C++

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

ll getCost(int idx, int l, int r, vector<ll> &a, vector<ll> &pref) {
    ll leftCnt = idx - l;
    ll leftSum = pref[idx] - pref[l];
    ll rightCnt = r - idx;
    ll rightSum = pref[r + 1] - pref[idx + 1];

    return a[idx] * leftCnt - leftSum + rightSum - a[idx] * rightCnt;
}

int main(int argc, char *argv[]) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, q;
    cin >> n >> q;

    vector<ll> a(n), pref(n + 1);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        pref[i + 1] = a[i] + pref[i];
    }

    while (q--) {
        ll L, R;
        cin >> L >> R;

        int l = lower_bound(a.begin(), a.end(), L) - a.begin();
        int r = upper_bound(a.begin(), a.end(), R) - a.begin() - 1;

        if (l >= r) {
            cout << "0\n";
            continue;
        }

        int m = (l + r) >> 1;
        ll lCost = getCost(l, l, r, a, pref);
        ll rCost = getCost(r, l, r, a, pref);
        ll mCost = getCost(m, l, r, a, pref);

        cout << max(lCost, rCost) - mCost << "\n";
    }

    return 0;
}