连号区间数

布满荆棘的人生 2024-03-29 15:07 59阅读 0赞

## 连号区间数 ##

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

在 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\]

时/空限制：1s / 64MB  
总通过数：8851  
总尝试数：14791  
来源：第四届蓝桥杯省赛C++B组,第四届蓝桥杯省赛JAVAB组

**算法思路**  
这个题的关键是 看懂题目 题目里面说的是 在 1∼N 的某个排列 这个排列的意思是 没有重复的数字  
也就是说 如果 一段连续的数字 最大的数字 - 最小的数字 = 这段数字的长度 - 1那么代表这段数字  
是符合题目要求的 因为没有重复的数字

**提交代码**  
C++

/*
    这个题的关键是 看懂题目 题目里面说的是 在 1∼N 的某个排列 这个排列的意思是 没有重复的数字
    也就是说 如果 一段连续的数字 最大的数字 - 最小的数字 = 这段数字的长度 - 1那么代表这段数字
    是符合题目要求的 因为没有重复的数字
    */
    #include<bits/stdc++.h>
    using namespace std;
    
    int INF = 1e9;
    const int N = 10010;
    int a[N];
    int res;
    
    int main()
    {
        
        int n;
        cin >> n;
        for (int i = 0; i < n; ++ i) scanf ("%d", &a[i]);
        for (int i = 0; i < n; ++ i)
        {
        
            int mav = -INF, miv = INF;
            int j;
            for (j = i; j < n; ++ j) 
            {
        
                mav = max(mav, a[j]);
                miv = min(miv, a[j]);
                if (mav - miv == j - i) res ++;
            }
        }
        cout << res;
        return 0;
    }

**Java**

import java.util.*;
    import java.io.*;
    
    public class Main
    {
        
        static int INF = (int)1e9;
        static int [] a = new int [10010];
        static int res, n;
        
        public static void main(String[] args) throws IOException
        {
        
            BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
            n = Integer.parseInt(reader.readLine());
            String [] strs = reader.readLine().split(" ");
            for (int i = 0; i < n; ++ i) a[i] = Integer.parseInt(strs[i]);
            for (int i = 0; i < n; ++ i)
            {
        
                int j;
                int mav = -INF, miv = INF;
                for (j = i; j < n; ++ j)
                {
        
                    mav = Math.max(mav, a[j]);
                    miv = Math.min(miv, a[j]);
                    if (mav - miv == j - i) res ++;
                }
            }
            System.out.println(res);
        }
    }