g595 - 1. 修補圍籬

🔗 前往 ZeroJudge 原題

題目描述

題目描述一個農場的圍籬，圍籬由 n 個高度不一的圍籬組成。有些圍籬被吹斷了，高度為 0。農場主人需要修補這些圍籬，修補策略是將斷掉的圍籬的高度設為其相鄰左右圍籬的較小高度。題目要求計算修補所有斷掉的圍籬所需的總成本，即新增的圍籬長度總和。

解題思路

這題的解題思路是貪婪演算法。我們遍歷圍籬，如果遇到高度為 0 的圍籬，則將其高度設為其相鄰左右圍籬的較小高度，並計算修補所需的成本（即新高度減去原高度，原高度為 0）。為了處理邊界情況，我們在圍籬的兩端添加了虛擬的圍籬，其高度等於相鄰的真實圍籬的高度。

複雜度分析

• 時間複雜度: O(n)
• 空間複雜度: O(n)

程式碼

#include <iostream>
using namespace std;
int a[205],n,ans;
int main(){
	cin >> n;
	for(int i=1;i<=n;++i){
		cin >> a[i];
	}
	a[0]=a[2];
	a[n+1]=a[n-1];
	for(int i=1;i<=n;++i){
		if(a[i]==0){
			ans+=min(a[i-1],a[i+1])-a[i];
			a[i]=min(a[i-1],a[i+1]);
		}
	}
	cout << ans;
}