蓝桥杯 连号区间【枚举】

题目链接：1210. 连号区间

小明这些天一直在思考这样一个奇怪而有趣的问题：在 1∼N的某个排列中有多少个连号区间呢？

这里所说的连号区间的定义是：如果区间 [L,R]里的所有元素（即此排列的第 L 个到第 R 个元素）递增排序后能得到一个长度为 R−L+1的“连续”数列，则称这个区间连号区间。当 N很小的时候，小明可以很快地算出答案，但是当 N变大的时候，问题就不是那么简单了，现在小明需要你的帮助。

输入格式 第一行是一个正整数 N，表示排列的规模。 第二行是 N个不同的数字 Pi，表示这 N个数字的某一排列。

输出格式 输出一个整数，表示不同连号区间的数目。

数据范围 1≤N≤10000, 1≤Pi≤N

输入样例1： 4 3 2 4 1

输出样例1： 7

输入样例2： 5 3 4 2 5 1

输出样例2： 9

样例解释 第一个用例中，有 7个连号区间分别是：[1,1],[1,2],[1,3],[1,4],[2,2],[3,3],[4,4] 第二个用例中，有 9 个连号区间分别是：[1,1],[1,2],[1,3],[1,4],[1,5],[2,2],[3,3],[4,4],[5,5]

程序说明：

如何判断区间是连续的？ 设区间左端点下标为 i，右端点下标为 j，则 j - i 为区间的长度。求出区间内的最大值max和最小值min，若max - min == j - i，则为连续的区间。 然后双指针枚举所有的区间，判断是否满足条件。

代码如下：

#include <iostream> using namespace std; const int N = 10010; int n, a[N], res; int main() { cin>>n; for(int i = 0; i < n; i++) cin>>a[i]; for(int i = 0; i < n; i++) { int max1 = -1e9, min1 = 1e9; for(int j = i; j < n; j++) { max1 = max(max1, a[j]); min1 = min(min1, a[j]); if(max1- min1 == j - i) { res++; } } } cout<<res; return 0; }