P1009 【挑战题】连号区间数

题目描述

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

在 1∼N 的某个排列中有多少个连号区间呢？

这里所说的连号区间的定义是：

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

思路

这里引用一下@TomAnderson(SU)老师的讲解：

“因为序列中的元素各不相同，所以选取任意区间[L,R]，区间中最大值maxx和最小值minn，一定为区间中数字排序后最左以及最右元素，若[L,R]为连续区间，maxx-minn+1就等于区间[L,R]之间元素个数，故可以此为依据，判断当前枚举区间，是否为连续区间。”

参考代码

#include <iostream>//hetao3097453
#include <algorithm>
using namespace std;
int a[10001],num,maxx,minn;
int main()
{
    int n;
    cin >> n;
    for(int i = 1;i <= n;i++)
    {
        cin >> a[i];
    }
    for(int i = 1;i <= n;i++)
    {
        maxx = -1;
        minn = 10001;
        for(int j = i;j <= n;j++)
        {
            maxx = max(maxx,a[j]);
            minn = min(minn,a[j]);
            if(maxx - minn == j - i)
            {
                num++;
            }
        }
    }
    cout << num << endl;
    return 0;
}

hetao3097453(bililili @ 一钩出站)

2023年3月19日

(PS:没有写那么详细是应为这个点了)