本文涉及知识点

C++差分数组

C++前后缀分解

P7404家庭菜园

出自洛谷，我简述一下。

已知数组a，长度为n(1<=n<=2e5),1 <=a[i] <=1e9。一次操作如下：将a[i…j]全+1。问最少操作多少次，使得a成为山形数组，即存在k，a[0…k]严格递增，a[k…]严格递减。

前后缀分解+差分数组（错误解法）

n = a.length

pre[i]记录将a长度为i的前缀转成严格递增需要的最少次数，np[i]记录此时a[i-1]的值。

suff[i]记录将a长度为i的后缀转成严格递减需要的最少次数，ns[i]类似np。可以转化成a的转置数组的前缀。

从0到n，枚举i。j = N-i。

如果np[i]== ns[i]，则转成 左半长为i的山形数组需要的操作次数为：pre[i]+suff[j]+1

否则，转成左半长为i或i+1的山形数组需要的操作次数为：pre[i]+suff[i]。前缀的最后一个元素和后缀的第一个元素，谁大谁是山顶。

如何求前缀递增的次数

pre[0] = 0

如果a[i] > a[i-1] 不需要操作。 否则 a[i…]都操作 a[i-1]+1-a[i]次。

为什么选择a[i…]而不是a[i…j]，如果后置是严格递增，前者也是。

由于a[i]后面的元素都增加了相同的数，所以后面的a[i]-a[i-1]都不变。

即求差分数组为正元素之和。

错误原因：{2,1,4,1,2} 直接将{2,1,4}提升两次。

正确解法

左边的操作是：[x1…i]加一，右边的操作是[ i…x2] ，一定可以合并成[x1

⋯

\cdots

⋯x2]

i从1到n

令 j = n+1- i，cur = max(pre[i],suff[j])

代码

核心代码

<code>#include <iostream>

#include <sstream>

#include <vector>

#include<map>

#include<unordered_map>

#include<set>

#include<unordered_set>

#include<string>

#include<algorithm>

#include<functional>

#include<queue>

#include <stack>

#include<iomanip>

#include<numeric>

#include <bitset>

using namespace std;

class Solution { -- -->

public:

long long Cal(const vector<int> a) {

auto PreSum = [](const vector<int>& nums) {

vector<long long> ret = { 0,0 };

for (int i = 1; i < nums.size(); i++) {

const int iAdd = max(0,nums[i - 1]+1 - nums[i]);

ret.emplace_back(ret.back() + iAdd);

}

return ret;

};

auto preSum = PreSum(a);

auto suff = PreSum( vector<int>(a.rbegin(), a.rend()));

long long ret = 2e18;

for (int i = 1; i <= a.size(); i++) {

const int j = a.size()+1 - i;

const auto cur = max(preSum[i],suff[j]);

ret = min(ret, cur);

}

return ret;

}

};

int main() {

//freopen("./a.in", "r", stdin);

//freopen("./output.txt", "a", stdout);

int N;

scanf("%d", &N);

vector<int> a(N );

for (int i = 0; i < N; i++) {

scanf("%d", &a[i]);

}

auto res = Solution().Cal(a);

printf("%lld", res);

return 0;

}

单元测试

vector<int> a;

TEST_METHOD(TestMethod1)

{

a = { 1 };

auto res = Solution().Cal(a);

AssertEx(0LL, res);

}

TEST_METHOD(TestMethod2)

{

a = { 1,2 };

auto res = Solution().Cal(a);

AssertEx(0LL, res);

}

TEST_METHOD(TestMethod3)

{

a = { 2,1 };

auto res = Solution().Cal(a);

AssertEx(0LL, res);

}

TEST_METHOD(TestMethod4)

{

a = { 4,1,1 };

auto res = Solution().Cal(a);

AssertEx(1LL, res);

}

TEST_METHOD(TestMethod5)

{

const int E9 = 1'000'000'000;

a = { E9,1,E9,1,E9,1,E9,1,E9,1,E9 };

auto res = Solution().Cal(a);

AssertEx(3LL*E9, res);

}

TEST_METHOD(TestMethod11)

{

a = { 3,2,2,3,1 };

auto res = Solution().Cal(a);

AssertEx(3LL, res);

}

TEST_METHOD(TestMethod12)

{

a = { 9,7,5,3,1 };

auto res = Solution().Cal(a);

AssertEx(0LL, res);

}

TEST_METHOD(TestMethod13)

{

a = { 2021, 2021 };

auto res = Solution().Cal(a);

AssertEx(1LL, res);

}

TEST_METHOD(TestMethod14)

{

a = { 12,2,34,85,4,91,29,85 };

auto res = Solution().Cal(a);

AssertEx(93LL, res);

}

TEST_METHOD(TestMethod15)

{

a = { 2,1,4,1,1 };

auto res = Solution().Cal(a);

AssertEx(2LL, res);

}

扩展阅读

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。

https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程

https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17

或者 操作系统：win10 开发环境： VS2022 C++17

如无特殊说明，本算法用**C++**实现。