【題解】ZeroJudge c779: 106北二4.盆栽展覽

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=c779
【解題想法】Greedy

#include <iostream>
#include <vector>
using namespace std;

int n, a, d, ans;
vector <int> v;

int main() {
    while (cin >> a){
        v.push_back(a);
    }
    d = v.back();
    v.pop_back();
    n = v.size();
    for (int i = 1; i < n; i++){
        if (v[i-1]-d > v[i]){
            ans += v[i-1]-v[i]-d;
            v[i] = v[i-1]-d;
        }
    }
    for (int i = n-2; i >= 0; i--){
        if (v[i+1]-d > v[i]){
            ans += v[i+1]-v[i]-d;
            v[i] = v[i+1]-d;
        }
    }
    cout << ans << "\n";
}

Python code (credit: Amy Chou, 8/30/2020)

A = list(map(int, input().split()))
d = int(input())
n = len(A)
ans = 0
for i in range(1, n):
    if A[i] < A[i-1] - d:
        ans += A[i-1] - d - A[i]
        A[i] = A[i-1] - d

for i in range(n-2, -1, -1):
    if A[i] < A[i+1] - d:
        ans += A[i+1] - d - A[i]
        A[i] = A[i+1] - d

print(ans)
分享本文 Share with friends