首页 > 编程语言 >【C++ 差分数组 前后缀分解】P7404家庭菜园

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

时间:2024-09-21 17:22:12浏览次数:11  
标签:AssertEx P7404 auto Cal Solution C++ 后缀 res include

本文涉及知识点

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

标签:AssertEx,P7404,auto,Cal,Solution,C++,后缀,res,include
From: https://blog.csdn.net/he_zhidan/article/details/142300356

相关文章

  • C++猫国建设者1.0.0.1
    最近我游玩猫国建设者游戏,让我灵感打发,于是用C++做了一个以后会慢慢更新代码如下:#include<iostream>#include<cstdio>#include<string>#include<algorithm>#include<cmath>#include<cstdlib>#include<ctime>#include<windows.h>#include&l......
  • C++ 使用范围 for 遍历多维数组用引用
    intmain(){constexprsize_trowCnt=3,colCnt=4;intia[rowCnt][colCnt];//使用for循环遍历初始赋值for(size_ti=0;i!=rowCnt;++i){for(size_tj=0;j!=colCnt;++j){ia[i][j]=i*colCnt+j......
  • C++ 数组的 auto 和 decltype
    当使用数组作为一个auto(参见2.5.2节,第61页)变量的初始值时,推断得到的类型是指针而非数组:intia[]={0,1,2,3,4,5,6,7,8,9};//ia是一个含有10个整数的数组autoia2(ia);//ia2是一个整型指针,指向ia的第一个元素ia2=42;......
  • vector--C++
    文章目录一、vector1、vector的介绍及使用1.1、vector的介绍1.2、vector的使用1.3、vector的定义1.4、vectoriterator的使用1.5、vector空间增长问题1.6、vector增删查改1.7、vector迭代器失效问题(重点)1.8、指定位置元素的删除操作--erase2、注意:Linux下,g++编译器......
  • C++ 数组声明和初始化
    显式初始化数组元素如果指明了维度,那么初始值的总数量不应该超出指定的大小。如果维度比提供的初始值数量大,则用提供的初始值初始化靠前的元素,剩下的元素被初始化成默认值(参见3.3.1节,第88页):constunsigneds=3;intial[sz]={0,1,2};//含有3个元素的数组,元素值分......
  • C++ 知识要点:I/O 模型
    1.使用同步IO模型实现的Reactor模式的工作流程(以epoll_wait为例)在Reactor模式中,主线程(也称为事件循环或分发器)负责监听和分发事件,工作线程负责处理具体的业务逻辑。以下是使用epoll_wait实现Reactor模式的工作流程,详细描述了事件的处理过程:1.主线程往epoll......
  • c++第3课
    #include<bits/stdc++.h>usingnamespacestd;intmain(){ inta=0; a=a+10; a=a+1; cout<<a; return0;}这叫累加,注意,cout<<a;这里不要加括号,不然输出结果会这样子:a这是因为加括号只输出a,而不加括号则输出11。1.取出4123的十位想要取出4123的十位就要用到/和%,......
  • c++算法 枚举———百钱白鸡问题
    前言枚举,是一种最基本的算法思想,通过穷举枚举出所有的可能,再加以比较。枚举算法适用于问题规模较小、解空间可穷举的情况。它的优点是简单直观,不需要复杂的数学推导,易于实现。但是,对于问题规模较大的情况,枚举算法的时间复杂度可能会非常高,效率较低。接下来会介绍两个百钱白......
  • 【C++篇】C++类与对象深度解析(六):全面剖析拷贝省略、RVO、NRVO优化策略
    文章目录C++类与对象前言读者须知RVO与NRVO的启用条件如何确认优化是否启用?1.按值传递与拷贝省略1.1按值传递的概念1.2示例代码1.3按值传递的性能影响1.3.1完全不优化1.4不同编译器下的优化表现1.4.1VisualStudio2019普通优化1.4.2VisualStudio2022激进......
  • 【c++】动态内存管理
    ......