题解 P5019 【铺设道路】
引领天下
2018-11-13 22:06:34
这题目就我一个人模拟吗？
普及蒟蒻，不会好算法，就来说一发模拟吧
首先一个贪心：
# 每次选一个连续正深度的坑的区间去填
为什么呢？因为只有这样，才能保证**我每次填坑的数量最多，不会造成浪费（即可以一天解决的问题我2天解决）**，也就是保证填的天数最少
于是得到了$ O(n^2* sum(a[1...n])) $，嗯，超时成什么样我就不说了
于是优化：
观察下面的表：
| d[1] | d[2] | d[3] | d[4] | d[5] | d[6] | d[7] |
| :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: |
| 1 | 4 | 3 | 3 | 4 | 3 | 3 |
| 0 | 3 | 2 | 2 | 3 | 2 | 2 |
| 0 | 2 | 1 | 1 | 2 | 1 | 1 |
| 0 | 1 | 0 | 0 | 1 | 0 | 1 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
可以发现，第2行与第3行实际上是重复的
在本例中，只重了2行；
如果重个10000，100000行呢？
那么你的程序就会T。
如何优化？
不难发现，我们填坑的过程是有规律的；
于是就有了优化：
**每次循环必然要彻底填掉至少1个坑**
那么，实现就很简单了：
在找**连续整数的时候，顺便查找最小值**，然后区间减最小值，完成目标。
到此为止，你已经拿到80分了
还有两个点什么情况？
因为，尽管我们优化了，整个复杂度还是$ O(n^{2}) $，是会T的
再优化！
我们可以发现，**当我们找区间的开始的时候，其实是有单调性的**
# 即：我下一次填坑的起始点一定在本次填坑的范围中
那么在模拟减的时候就可以顺便找下一次的开始了。
你也许发现了一个问题：
> 一遍坑全部填平了怎么办？
没事，设定一个极值，最后判一下，如果没变的话就从本次的结束点往后找啦~
于是复杂度降到了$ O(n+\text{常数}) $，就AC了
代码：
```cpp
#include <bits/stdc++.h>
using namespace std;
int n,d[100005],q=1;
long long s,ans;
int main(){
scanf ("%d",&n);
for (int i=1;i<=n;i++)scanf ("%d",&d[i]),s+=d[i];//读入，统计和
int b=1;
while (d[b]==0)b++;//找开端
q=b;//下一个开端
while (s){
b=q;
int e=b,mn=1<<20;
while (d[e])mn=min(mn,d[e]),e++;//找最小值
ans+=mn,s-=mn*(e-b);//花mn天干，总和减去填的所有
q=1<<20;
for (int i=e-1;i>=b;i--){d[i]-=mn;if (d[i]>0)q=i;}//模拟减，同时找下一次的开端
if (q==1<<20)for (q=e+1;q<=n;q++)if(d[q]>0)break;
}
printf ("%d",ans);
}
```