【C++贪心】P8087 『JROI-5』Interval|普及+

闻缺陷则喜何志丹

1087人浏览 · 2025-10-07 17:00:00

闻缺陷则喜何志丹 · 2025-10-07 17:00:00 发布

本文涉及知识点

C++贪心

『JROI-5』Interval

题目背景

小 C 喜欢带有区间操作的数据结构，因为这样的题总会有一档好写的 $\mathcal{O}\left(n^2\right)$ 部分分。

题目描述

本题读入量较大，建议使用较快的读入方式，可以参考赛时公告板

小 C 有一个长度为 $n$ 的序列 $a$ ，第 $i$ 项为 $a_i$ 。

$a$ 是一个 $1\sim n$ 的排列（即 $1\sim n$ 在 $a$ 中各出现一次）。

定义 $\operatorname{Mex}_{l,r}$ 为 $\{a_l,a_{l+1}, \cdots,a_{r-1},a_r\}$ 中没有出现过的最小正整数。

例如， $\operatorname{Mex}\{2,3\}=1,\operatorname{Mex}\{1,2,3\}=4$ 。

小 C 还有一个长度为 $n$ 的数列 $f$ 。

定义一个区间 $\left[l,r\right]$ 是合法的当且仅当
$f_{r-l+1}< \operatorname{Mex}_{l,r}$

小 C 希望你告诉他，最短的合法区间的长度是多少，特别的，如果没有区间合法，则输出 0。

输入格式

第一行一个正整数 $n$ 。

第二行 $n$ 个正整数 $a_1,a_2,\cdots,a_n$ 。

第三行 $n$ 个正整数 $f_1,f_2,\cdots,f_n$ 。

输出格式

一行一个整数，表示最短的合法区间长度。

样例 #1

样例输入 #1

5
2 3 1 5 4
2 2 3 4 5

样例输出 #1

样例 #2

样例输入 #2

5
2 3 1 5 4
1 2 2 4 5

样例输出 #2

样例 #3

样例输入 #3

5
1 3 4 2 5
6 7 8 9 10

样例输出 #3

样例 #4

样例输入 #4

见附件

样例输出 #4

见附件

提示

【样例解释】

对于 #1，容易发现 $\left[1,3\right]$ 是最短的合法区间。

对于 #2，容易发现 $\left[3,3\right]$ 是最短的合法区间。

对于 #3，容易发现没有合法的区间。

对于 $10\%$ 的数据，满足 $1\leq n\leq 100$ 。

对于 $20\%$ 的数据，满足 $1\leq n\leq 1000$ 。

对于另外 $10\%$ 的数据，满足 $f$ 不升，即满足 $f_1\geq f_2\geq\cdots\geq f_n$ ，且 $1\leq n\leq 10^6$ 。

对于 $100\%$ 的数据，满足 $1\leq n\leq 4\times 10^6,1\leq f_i\leq 10^9$ 。

贪心

inxs[i]记录i在a中的下标。
mex的取值范围[1,n+1]
我们枚举mex为i的最短iMin最长iMax子数组。
i是1,如果n为1，不存在mex为1的非空子数组，否则iMin=1。iMax = max(inxs[i],n-inxs[i]-1)。由于f >0，故mex为1,一定不是合法子数组。
i $\in$ [2,n]，子数组包括所有小于i的数，即left = 小于i的数的最小下标，r = 小于i的数的最大下标。如果inxs[i] $\in$ [left,r]则，不存在mex为i的子数组。否则：
iMin = r - left+1, 如果inxs[i] 大于r，iMax = inxs[i] ，否则iMax = n - inxs[i]-1。
i = n+1,则长度必定为n。
用差分数组或线段树或树状数组，记录各长度的最大mex。枚举各长度的mex，看是否大于f。
left,r的迭代过程：left = min(left,inxs[i]),r = max(r,inxs[i])

关于超内存的解放方法

总内存128M ，N为4e6时，一个长度为N的有序集合或哈希集合就超内存了。一个长度为N的向量占用15M。估计线段树，尤其是使用封装类或模板的，高几率超过内存。
差分数组解法，之所以用有序集合而不是向量，有两个原因：一，方便取最大值。二，方便删除。
解决方法：一，由于是升序，容器尾就是最大值。二，删除用懒删除，只记录需要删除的次数。如果容器顶刚好是要删除元素，则删除。

代码

核心代码

内存超了，4e6个元素，内存只有1e9。一个元素，只有大约30个字节，太严格了。

#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 <math.h>
#include <climits>
#include<assert.h>
#include<cstring>

#include <bitset>
using namespace std;



template<class T = int>
vector<T> Read(int n,const char* pFormat = "%d") {
	vector<T> ret;
	T d ;
	while (n--) {
		scanf(pFormat, &d);
		ret.emplace_back(d);
	}
	return ret;
}

template<class T = int>
vector<T> Read( const char* pFormat = "%d") {
	int n;
	scanf("%d", &n);
	vector<T> ret;
	T d;
	while (n--) {
		scanf(pFormat, &d);
		ret.emplace_back(d);
	}
	return ret;
}

string ReadChar(int n) {
	string str;
	char ch;
	while (n--) {
		do
		{
			scanf("%c", &ch);
		} while (('\n' == ch));
			str += ch;
	}
	return str;
}

class Solution {
		public:
			int Ans(vector<int> a, vector<int> f) {
				const int N = a.size();
				vector<int> inxs(N + 1);
				for (int i = 0; i < N; i++) {
					inxs[a[i]] = i;
				}
				vector<vector<int>> diff(N + 2);
				auto Record = [&](int iMin, int iMax,int mex) {
					if (iMin > iMax) { return; }
					diff[iMin].emplace_back(mex);
					diff[iMax + 1].emplace_back(-mex);
				};
		
				int left = inxs[1], r = inxs[1];	
				for (int i = 2; i <= N; i++) {
					const int inx = inxs[i];
					if ((inx > left)&&(inx < r )) { continue; }
					const int len = r - left + 1;
					const int iMax = (inx > r) ? inx : (N - inx - 1);					
					Record(len, iMax,i);
					left = min(left, inx);
					r = max(r, inx);
				}
				Record(N, N, N + 1);
				multiset<int> mex;
				for (int i = 1; i <= N; i++) {
					for (const auto& j : diff[i]) {
						if (j > 0) { mex.emplace(j); }
						else { mex.erase(mex.find(-j)); }
					}
					if (mex.size() && (*mex.rbegin() > f[i - 1])) { return i; }
				}
				return 0;
			}
		};

int main() {
#ifdef _DEBUG
	freopen("a.in", "r", stdin);
#endif // DEBUG
	int n;
	scanf("%d", &n);
	auto a = Read<int>(n);
	auto f = Read<int>(n);
#ifdef _DEBUG
	
#endif	
	auto res = Solution().Ans(a,f);
	cout << res << endl;
	return 0;
}

单元测试

#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 <math.h>
#include <climits>
#include<assert.h>
#include<cstring>

#include <bitset>
using namespace std;



template<class T = int>
vector<T> Read(int n,const char* pFormat = "%d") {
	vector<T> ret;
	T d ;
	while (n--) {
		scanf(pFormat, &d);
		ret.emplace_back(d);
	}
	return ret;
}

template<class T = int>
vector<T> Read( const char* pFormat = "%d") {
	int n;
	scanf("%d", &n);
	vector<T> ret;
	T d;
	while (n--) {
		scanf(pFormat, &d);
		ret.emplace_back(d);
	}
	return ret;
}

string ReadChar(int n) {
	string str;
	char ch;
	while (n--) {
		do
		{
			scanf("%c", &ch);
		} while (('\n' == ch));
			str += ch;
	}
	return str;
}

class Solution {
		public:
			int Ans(vector<int> a, vector<int> f) {
				const int N = a.size();
				vector<int> inxs(N + 1);
				for (int i = 0; i < N; i++) {
					inxs[a[i]] = i;
				}
				vector<vector<int>> diff(N + 2);
				auto Record = [&](int iMin, int iMax,int mex) {
					if (iMin > iMax) { return; }
					diff[iMin].emplace_back(mex);
					diff[iMax + 1].emplace_back(-mex);
				};
		
				int left = inxs[1], r = inxs[1];	
				for (int i = 2; i <= N; i++) {
					const int inx = inxs[i];
					if ((inx > left)&&(inx < r )) { continue; }
					const int len = r - left + 1;
					const int iMax = (inx > r) ? inx : (N - inx - 1);					
					Record(len, iMax,i);
					left = min(left, inx);
					r = max(r, inx);
				}
				Record(N, N, N + 1);
				multiset<int> mex;
				for (int i = 1; i <= N; i++) {
					for (const auto& j : diff[i]) {
						if (j > 0) { mex.emplace(j); }
						else { mex.erase(mex.find(-j)); }
					}
					if (mex.size() && (*mex.rbegin() > f[i - 1])) { return i; }
				}
				return 0;
			}
		};

int main() {
#ifdef _DEBUG
	freopen("a.in", "r", stdin);
#endif // DEBUG
	int n;
	scanf("%d", &n);
	auto a = Read<int>(n);
	auto f = Read<int>(n);
#ifdef _DEBUG
	
#endif	
	auto res = Solution().Ans(a,f);
	cout << res << endl;
	return 0;
}

内存通过

#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 <math.h>
#include <climits>
#include<assert.h>
#include<cstring>

#include <bitset>
using namespace std;


template<class T = int>
vector<T> Read(int n,const char* pFormat = "%d") {
	vector<T> ret(n);
	for(int i=0;i<n;i++) {
		scanf(pFormat, &ret[i]);	
	}
	return ret;
}

template<class T = int>
vector<T> Read( const char* pFormat = "%d") {
	int n;
	scanf("%d", &n);
	vector<T> ret;
	T d;
	while (n--) {
		scanf(pFormat, &d);
		ret.emplace_back(d);
	}
	return ret;
}

string ReadChar(int n) {
	string str;
	char ch;
	while (n--) {
		do
		{
			scanf("%c", &ch);
		} while (('\n' == ch));
			str += ch;
	}
	return str;
}

class Solution {
		public:
			int Ans(vector<int>& a, vector<int>& f) {
				const int N = a.size();
				vector<int> inxs(N + 1);
				for (int i = 0; i < N; i++) {
					inxs[a[i]] = i;
				}
				vector<pair<int,int>> add,sub;
				auto Record = [&](int iMin, int iMax, int mex) {
					if (iMin > iMax) { return; }
					add.emplace_back(make_pair( iMin,mex ));
					sub.emplace_back(make_pair(iMax+1,mex));
				};

				int left = inxs[1], r = inxs[1];
				for (int i = 2; i <= N; i++) {
					const int inx = inxs[i];
					if ((inx > left) && (inx < r)) { continue; }
					const int len = r - left + 1;
					const int iMax = (inx > r) ? inx : (N - inx - 1);
					Record(len, iMax, i);
					left = min(left, inx);
					r = max(r, inx);
				}
				Record(N, N, N + 1);
				sort(add.begin(), add.end(), greater<>());
				sort(sub.begin(), sub.end(),greater<>());
				vector<int> has, needErase(N + 2);	
				for (int i = 1; i <= N; i++) {
					while (add.size() && (add.back().first == i)) {
						has.emplace_back(add.back().second);
						add.pop_back();
					}
					while (sub.size() && (sub.back().first == i)) {
						needErase[sub.back().second]++;
						sub.pop_back();
					}
					while (has.size() && (needErase[has.back()] > 0)) {
						needErase[has.back()]--;
						has.pop_back();
					}
					if (has.size() && (has.back() > f[i - 1])) { return i; }
				}
				return 0;
			}
		};

int main() {
#ifdef _DEBUG
	freopen("a.in", "r", stdin);
#endif // DEBUG
	int n;
	scanf("%d", &n);
	auto a = Read<int>(n);
	auto f = Read<int>(n);
#ifdef _DEBUG
	
#endif	
	auto res = Solution().Ans(a,f);
	cout << res << endl;
	return 0;
}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功

视频课程

先学简单的课程，请移步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++**实现。

AI Agent技术社区

Agent 垂直技术社区，欢迎活跃、内容共建。

更多推荐

上下文窗口越大，越要克制往里面塞东西

AI Agent技术社区

KMP全栈开发：从Android跨端到AI Agent的技术演进与实战

Kotlin Multiplatform（KMP）已从Android跨端工具演进为端云一体全栈开发底座。依托expect/actual机制实现多端业务逻辑复用，结合Ktor打通客户端与后端，借助Koog框架摆脱Python依赖，支持纯Kotlin开发AI Agent。文章梳理KMP从原生Android开发、前后端全栈到AI智能体的技术演进，介绍端云协同智能体架构与标准项目分层方案，对比传统多语言架