本文涉及知识点
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])
代码
核心代码
#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++**实现。