历届试题连号区间数

我就是我 2023-07-13 13:59 18阅读 0赞

# 试题 历届试题 连号区间数 #

资源限制
    时间限制：1.0s   内存限制：256.0MB

## 问题描述 ##

小明这些天一直在思考这样一个奇怪而有趣的问题：

在1~N的某个全排列中有多少个连号区间呢？这里所说的连号区间的定义是：

如果区间\[L, R\] 里的所有元素（即此排列的第L个到第R个元素）递增排序后能得到一个长度为R-L+1的“连续”数列，则称这个区间连号区间。

当N很小的时候，小明可以很快地算出答案，但是当N变大的时候，问题就不是那么简单了，现在小明需要你的帮助。

## 输入格式 ##

第一行是一个正整数N (1 <= N <= 50000), 表示全排列的规模。

第二行是N个不同的数字Pi(1 <= Pi <= N)， 表示这N个数字的某一全排列。

## 输出格式 ##

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

## 样例输入1 ##

4
    3 2 4 1

## 样例输出1 ##

## 样例输入2 ##

5
    3 4 2 5 1

## 样例输出2 ##

## 思路： ##

区间\[L, R\] 里的所有元素（即此排列的第L个到第R个元素）递增排序后能得到一个长度为R-L+1的“连续”数列，则称这个区间连号区间。

\#思路很简单：  
是连号区间的话，**区间长度**一定等于这个区间的**最大值-最小值 +1**

区间\[l,r\]，所以让每个位置为l，再枚举r，同时更新区间的最值。  
因为我数组下标是从0开始，所以**ans += (j-i) == maxx-minx;**

## 代码： ##

#include <cstdio>
    #include <iostream>
    using namespace std;
    const int N = 5e4+5;
    int a[N];
    int main()
    {
        
        int n;
        scanf("%d",&n);
        for(int i = 0; i < n; i++)
        {
        
            scanf("%d",&a[i]);
        }
        long long ans = n;
        for(int i = 0; i < n; i++)
        {
        
            int minx = a[i];
            int maxx = a[i];
            for(int j = i+1; j < n; j++)
            {
        
                minx = min(minx,a[j]);
                maxx = max(maxx,a[j]);
                ans += (j-i) == maxx-minx;
            }
        }
        printf("%lld\n",ans);
        return 0;
    }