P5019-铺设道路 - 从萌新到萌新的成长历程

题目传送门

题目思路

思路本质上是个贪心，每次都选最大的覆盖区域即可，思路是找到当前最小的那个，然后查找以他为中心的一个范围，然后覆盖。

#include <iostream>
#include <vector>
using namespace std;

int n;
vector<int> d;
int sum = 0;

void fill(int l, int r)
{
    sum++;
    for (int i = l; i <= r; i++)
        d[i] -= 1;
}

bool isempty()
{
    for (int i = 0; i < n; i++)
        if (d[i] != 0)
            return false;
    return true;
}

int main()
{
    cin >> n;
    d = vector<int>(n);
    for (int i = 0; i < n; i++)
        cin >> d[i];

    while (!isempty())
    {
        int l = 0;
        int r = n - 1;
        int p = 0;
        for (int i = 0; i < n; i++)
        {
            if ((d[i] < d[p] && d[i] != 0) || d[p] == 0)
                p = i;
        }
        for (int i = p; i >= 0; i--)
            if (d[i] != 0)
                l = i;
            else
                break;
        for (int i = p; i < n; i++)
            if (d[i] != 0)
                r = i;
            else
                break;
        fill(l, r);
    }
    cout << sum;
    return 0;
}

提交后7AC，3TLE，证明思路没问题，但是超时了，汗

查看代码，是O(n)级别，但是应该是相当于4n级别，看了看题解，大概要缩到2n才能过

好吧2n也不行，需要n级别，需要一定的奇技淫巧

最终应该使用差分做.

贴上证明链接：https://www.luogu.com.cn/article/u9pnje1i

AC代码

#include <iostream>
#include <vector>
using namespace std;

int n;
vector<int> d;
int sum = 0;

int main()
{
    cin >> n;
    d = vector<int>(n);
    cin >> d[0];
    sum += d[0];
    for (int i = 1; i < n; i++)
    {
        cin >> d[i];
        if (d[i] > d[i - 1])
            sum += d[i] - d[i - 1];
    }
    cout << sum;
    return 0;
}