20984 - Growing Vegetables is Fun 4

작성일 | In

  • 문제 설명

    일렬로 키가 각각 $L_1,L_2,\cdots,L_N$인 식물이 놓여있고, $[l,r]$구간에 물을 주면 $L_l,L_l+1,\cdots,L_r$이 1씩 증가하게 됩니다. 이런 상황에서 최소 횟수 $d$로 피라미드 모양을 만들려 할 때 $d$를 구하는 것이 문제입니다.

  • 해설

    우선 가장 길게 될 식물(피라미드의 정점)을 정합니다. 이후, 그 식물 앞으로는 증가수열, 뒤로는 감소수열이 되게끔 하는 최소 횟수를 $pref$, $suf$배열에 저장합니다. $x$를 가장 높은 식물로 키우는 최소 횟수는 $max(pref[x], suf[x]) +$식물 $x$를 $max(L_{x-1}, L_{x+1})+1$으로 키우는 횟수입니다. 이 중 최소를 구하면 됩니다. 시간복잡도는 $O(N)$입니다.

  • 코드

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n; cin >> n;
    vector<ll> a(n);
    for(int i=0; i<n; i++) {
        cin >> a[i];
    }
    vector<ll> pref(n), suf(n);
    for(int i=1; i<n; i++) {
        pref[i] = pref[i-1];
        if(a[i] > a[i-1]) continue;
        else {
            pref[i] += a[i-1] - a[i] + 1; 
        }
    } 
    for(int i=n-2; i>=0; i--) {
        suf[i] = suf[i+1];
        if(a[i] > a[i+1]) continue;
        else suf[i] += a[i+1] - a[i] + 1;
    }
    ll ans = LLINF;
    for(int i=0; i<n; i++) {
        ll v1 = 0; if(i) v1 = pref[i-1];
        ll v2 = 0; if(i+1<n) v2 = suf[i+1];
        ll m1 = 0; if(i) m1 = a[i-1];
        ll m2 = 0; if(i+1<n) m2 = a[i+1];
        ans = min(ans, max(v1, v2) + max(0LL, max(m1, m2) - a[i] + 1));
    }
    cout << ans << '\n';
}