[数据结构与算法]贪心算法——铺设道路

题目链接：

?题解：

这道题一开始我就一直在用暴力的方法解（分情况讨论：1.当没有平坦的到路段式找出最小值，所有数都减去它的值，此时此位置的值为0，然后再将该段道路分开两半，利用二分，递归直到将所有的值都减为0 。2.有平坦的路段的时候直接将该道路分为几段然后同上再利用二分，递归写），不仅麻烦，而且复杂度高。

后来我找到了一个方法：

因为当一个大坑被填的时候它旁边的小坑也会被填上，如果出现0说明它不用再填，也就是说在此以后的填坑区间不能跨过这个0所在的位置那么它周边的大坑就相对于其他坑孤立，只能单独填它，所需天数也就是这个大坑与小坑的差值，所以sum应该+这个差值。? ?

本题中我是假设从一开始而言前面的坑都被填上，然后再进行上述的算法。

#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
int fan[100005];
int main(){
    int n;
	cin>>n;
	int k=0,p=0;
	int sum=0;
	for(int i=1;i<=n;i++){
		cin>>k;
		if(k>p){
			sum+=k-p;
		}
		p=k;  //向前推进 
	}	
	cout<<sum<<endl; 
	return 0;
} 

?