连号区间数

GeekLiHua

发布于 2025-01-21 19:44:40

5300

代码可运行

文章被收录于专栏：JavaJava

运行总次数：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);
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2023-01-13，如有侵权请联系 cloudcommunity@tencent.com 删除

int