当前位置:首页 » 《随便一记》 » 正文

【C++ 差分数组 前后缀分解】P7404家庭菜园

21 人参与  2024年09月20日 14:42  分类 : 《随便一记》  评论

点击全文阅读


本文涉及知识点

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])

代码

核心代码

#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++**实现。


点击全文阅读


本文链接:http://zhangshiyu.com/post/162243.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

关于我们 | 我要投稿 | 免责申明

Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1