Seagull Population

문제

링크: Seagull Population

풀이

하한

답 $m$의 하한을 생각해 봅시다.

먼저 $i$번째 날에는 적어도 $b_i$마리가 있어야 하므로 $m \geq \max(b_i)$입니다.

문제가 원형이므로 $b_0 = b_n$으로 생각합시다.

$i$번째 날에 도착한 갈매기의 수를 $a_i$, 떠난 갈매기의 수를 $d_i$라 하면 $b_i = b_{i - 1} + a_i - d_i$입니다.

$a_i = b_i - b_{i - 1} + d_i$이므로 $a_i \geq b_i - b_{i - 1}$입니다. $a_i$의 정의상 $a_i \geq 0$이므로 $\sum a_i \geq \sum \max(0, b_i - b_{i - 1})$입니다.

따라서 $m \geq \sum \max(0, b_i - b_{i - 1})$입니다.

선형 풀이

만약 문제가 원형이 아니라면 큐를 이용해서 문제를 해결할 수 있습니다.

$i = 1$부터 $n$까지 반복합니다. 여기서는 문제가 선형이므로 $b_0 = 0$으로 생각합시다.

• $b_i > b_{i - 1}$이면 $i$를 $b_i - b_{i - 1}$만큼 큐에 넣습니다.
• $b_i < b_{i - 1}$이면 큐에서 $b_{i - 1} - b_i$개를 꺼내서 각각 끝점을 $i - 1$로 기록하고 출력합니다.

해당 방법으로 풀었을 때의 답을 $L$이라 합시다. $L = \sum \max(0, b_i - b_{i - 1})$입니다. 원형과 달리 $b_0 = 0$임에 주의합시다.

위 알고리즘에서 구간의 시작이 $1$인 것과 구간의 끝이 $n$인 것을 최대한 합치면 답이 됩니다.

합칠 조건

큐에 넣은 순서대로 갈매기에게 번호를 매겨봅시다.

$i$번 갈매기가 도착한 날을 $s_i$, 머무른 마지막 날을 $e_i$라 합시다.

$s_i = 1$인 갈매기와 $e_j = n$인 갈매기를 합치려면 $e_i < s_j$여야 합니다.

최대 매칭

첫 번째 날부터 $i$번째 날까지 도착한 갈매기의 누적 합을 $A_i$, $i$번째 날까지 떠난 갈매기의 누적 합을 $D_i$라 합시다.

$i$번째 날 섬에 있는 갈매기들은 $D_{i - 1} + 1$부터 $A_i$까지의 연속된 번호를 갖습니다. 이 구간의 크기는 정확히 $b_i$이므로 어떤 두 갈매기의 번호가 $\max(b_i)$ 이상 차이 난다면 그 두 갈매기는 겹치지 않으므로 합칠 수 있습니다.

이 성질에 의해 $k = \min(b_1, b_n, L - \max(b_i))$개를 서로 합칠 수 있습니다.

$i = 1$부터 $k$까지 $i$번 갈매기와 $L - k + i$번 갈매기를 서로 합쳐봅시다.

두 갈매기를 합치려면 $e_i < s_{L - k + i}$여야 합니다.

그런데 $(L - k + i) - i = L - k = L - \min(b_1, b_n, L - \max(b_i)) \geq \max(b_i)$이므로 두 갈매기는 항상 구간이 겹치지 않습니다.

따라서 두 갈매기를 합칠 수 있습니다.

최적 증명

$L - k = L - \min(b_1, b_n, L - \max(b_i)) = \max(L - b_1, L - b_n, \max(b_i)) = \max(\max(L - b_1, L - b_n), \max(b_i))$입니다.

원형 기준으로 $b_0 = b_n$이라 두면 $L = b_1 + \displaystyle\sum_{i = 2}^n \max(0, b_i - b_{i - 1})$입니다.

$m$의 하한 중 하나인 $\displaystyle\sum \max(0, b_i - b_{i - 1}) = \max(0, b_1 - b_n) + \displaystyle\sum_{i = 2}^n \max(0, b_i - b_{i - 1})$입니다.

만약 $b_1 \geq b_n$이라면 $\displaystyle\sum \max(0, b_i - b_{i - 1}) = L - b_n$이 됩니다.

만약 $b_1 < b_n$이라면 $\displaystyle\sum \max(0, b_i - b_{i - 1}) = L - b_1$이 됩니다.

따라서 $L - k$는 앞서 찾은 하한인 $\max(\max(b_i), \sum \max(0, b_i - b_{i - 1}))$와 같으므로 최적입니다.

코드

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
constexpr int LIMIT = 2e5;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n;
    cin >> n;
 
    vector<ll> b(n + 2);
    for (int i = 1; i <= n; i++) cin >> b[i];
 
    ll M = b[1];
    ll D = max(0LL, b[1] - b[n]);
    for (int i = 2; i <= n; i++) {
        M = max(M, b[i]);
        D += max(0LL, b[i] - b[i - 1]);
    }
 
    ll m = max(M, D);
    cout << m << '\n';
    if (m > LIMIT) return 0;
 
    queue<int> entry;
    vector<pair<int, int>> ans = {{0, 0}};
    for (int i = 1; i <= n + 1; i++) {
        if (b[i] > b[i - 1]) {
            for (int j = 0; j < b[i] - b[i - 1]; j++) entry.push(i);
        } else {
            for (int j = 0; j < b[i - 1] - b[i]; j++) {
                int f = entry.front();
                entry.pop();
 
                ans.emplace_back(f, i - 1);
            }
        }
    }
 
    int L = ans.size() - 1;
    int k = min({b[1], b[n], L - M});
 
    for (int i = k; i >= 1; i--) {
        ans[i].first = ans.back().first;
        ans.pop_back();
    }
 
    for (int i = 1; i <= L - k; i++) {
        auto [s, t] = ans[i];
        cout << s << ' ' << t << '\n';
    }
 
    return 0;
}