There is a farm with a fence of width N, and each section of the fence has its height H1 to HN.
Some sections of the fence have been broken. The farmer needs to repair these sections, but he has forgotten their original heights. To reduce costs, he will use the smaller height between the adjacent sections on the left and right sides of the broken sections to fill them in. You're asking for the total cost of repairs.
The problem ensures that there won't be two adjacent broken fences and that the broken fence might be located at the boundary.
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| The input contains two lines. The first line contains a positive integer N. The second line contains N integers separated by spaces, representing the heights H1, H2,…,HN.1～HN | Output a single positive integer representing the total length of the newly added fences. |
| 3 2 0 4 | 2 |
| 9 0 5 3 0 6 4 0 1 0 | 10 |
Thought Process
Store the heights of the fences in an array and run a for loop from 0 to N-1. If H[i] is 0, then determine which side (left or right) is lower and add it to the answer.
If the current index i is at the boundary (0 or N-1), there is no need to compare sizes; simply add the length of the other side's fence to the answer.
Sample Code－ZeroJudge G595: Repairing Fence
#include <iostream>
#include <vector>
using namespace std;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int N, ans = 0;
cin >> N;
vector<int>num;
for (int i = 0; i<N; i++)
{
int tmp;
cin >> tmp;
num.push_back(tmp);
}
for (int i = 0; i<N; i++)
{
if (num[i] == 0)
{
if (i == 0)
{
ans += num[i+1];
continue;
}
if (i == N-1)
{
ans += num[i-1];
continue;
}
ans += min(num[i+1], num[i-1]);
}
}
cout << ans << "\n";
}
//ZeroJudge G595
//Dr. SeanXD