题解 P5019 【铺设道路】

· · 题解

这题目就我一个人模拟吗？

普及蒟蒻，不会好算法，就来说一发模拟吧

首先一个贪心：

每次选一个连续正深度的坑的区间去填

为什么呢？因为只有这样，才能保证我每次填坑的数量最多，不会造成浪费（即可以一天解决的问题我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了

代码：

#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);
}