蓝桥杯历届试题 连号区间数

发表于由
问题描述

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

在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
7
样例输入2
5
3 4 2 5 1
样例输出2
9
解答：题意读起来很不舒服，实际上就是寻找任意一个字数列中包含连续的整数，例如“1”，“1，2，3”，“3，2”这种都算，输入例子中
3 2 1 4-》”3“  ”2“  ”4“  ”1“  ”3，2“  ”3，2，1“  ”3，2，1，4“  共7种，
编写代码时注意，

//注意，长度区间为1也是可行的

//虽然长度是j－i＋1但是跨度还是j－i

代码如下：

#include <iostream>

#include <queue>

#include <iomanip>

#include <math.h>

#include <vector>

#include <string>

#include <algorithm>

#include <map>

#include<cstring>

#include<ctype.h>

#include<math.h>

using namespace std;

int vx[1000];

//char A[1000];

//char B[1000];

int main(int argc, const char * argv[]) {

    int n;

    cin>>n;

    int *temp = new int[n];

    for(int i = 0 ; i < n;i++)

    {

        cin>>temp[i];

    }

    int R;

    int L;

    int count = 0;

    for(int i = 0 ; i < n;i++)

    {

        R = temp[i];

        L = temp[i];

        count++;//注意，长度区间为1也是可行的

        for(int j = i+1; j<n;j++)

        {

            if(R < temp[j])

                R = temp[j];

            if(L > temp[j])

                L = temp[j];

            if(R-L == j – i)//虽然长度是j－i＋1但是跨度还是j－i

                count++;

        }

    }

    cout<<count;

}

发表评论