蓝桥杯 1210. 连号区间数

文章目录

• • • 1210. 连号区间数

AcWing网站原题通道

1210. 连号区间数

题意分析：给我们1~N的排列，让我们求出这个排列中有多少个连号区间，，连号区间也就是对这个区间排序之后，相邻两数相差为1。先分析数据范围有105，那么我们可以使用时间复杂度为O(nlongn)的算法，如果想不出来可以考虑O(n2)的算法。

我们先来理一下暴力的思路：

for(枚举起点)
	for(枚举终点)
	{
		sort(); // 对起点和终点之间的区间排序
		chekc(); // 再次遍历检查相邻两数的差值是否为1
	}
           

对于上边暴力的做法，我们发现枚举起点和终点这步很难去优化，那么我们就可以考虑对判断是否是连号区间这部操作来进行优化。

我们先来找一下连号区间的性质：

题目说给我们的是

1~N

的排列，那么

1~N

之间的数肯定会不重不漏，那么如果我们要判断一个区间是否是连号区间，我们只需要判断这个区间里边最大值和最小值的差是否等于区间长度-1，如果等于就是连号区间；否则就不是。

举个例子：

（1）对于132来说，这个区间最大值3，最小值1，区间长度-1为2， max-min == 2 ，所以是连号区间

（2）对于142来说，这个区间最大值是4，最小值是1，区间长度-1为2 ， max - min = 3 ， 不等于区间长度-1，所以不是连号区间

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 10010 , INF = 1e8;
int a[N];

int main()
{
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    
    int res = 0;
    
    for(int i = 0; i < n; i++)
    {
        // 定义最大值和最小值
        int maxv = -INF , minv = INF;
        for(int j = i; j < n; j++)
        {
            maxv = max(maxv , a[j]);
            minv = min(minv , a[j]);
            // 判断是否是连号区间
            if(maxv - minv == j-i) res ++;
        }
    }
    
    cout << res << endl;
    
    return 0;
}