NO6---蓝桥杯JAVA---连号区间数

本文主要是介绍NO6---蓝桥杯JAVA---连号区间数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

在 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

本题主要考优化算法

其实正常思路 挨个在不同区间内比大小 找最值 与区间大小比较  但是它不能全部运行  在N=10003时出错

import java.util.Scanner;public class Main {public static Long N;public static int ans[]=new int[10003];public static Long count=(long) 0;public static void main(String[] args) {Scanner sc=new Scanner(System.in);N=sc.nextLong();sc.nextLine();for(int i=0;i<N;i++) {int t=sc.nextInt();ans[i]=t;}sc.close();for(int i=0;i<N;i++) {for(int j=i;j<N;j++) {int min=ans[i];int max=ans[i];for(int k=i+1;k<=j;k++) {if(ans[k]<min)min=ans[k];if(ans[k]>max)max=ans[k];}int ee=j-i;if(ee==(max-min))count++;}}System.out.println(count);}}

所以我上网找了一下JAVA的专属语句，以及可以把输入的数组变成字符串，减少消耗，方便分区

bufferedreader: 从字符输入流读取文本，缓冲字符，以提供字符，数组和行的高效读取 ；

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;public class Main {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));public static int arr[]=new int[10003];public static int res=0;public static void main(String[] args) throws Exception {int n = Integer.parseInt(br.readLine());String[] str = br.readLine().split(" ");for (int i=1; i<=n; i++) {arr[i] = Integer.parseInt(str[i-1]); //设定区间下标从1开始，所以i-1}for (int i=1; i<=n; i++) {int minv = Integer.MAX_VALUE;int maxv = Integer.MIN_VALUE;for (int j=i; j<=n; j++) {minv = Math.min(minv,arr[j]);maxv = Math.max(maxv,arr[j]);if (maxv - minv == j - i) {res ++;}}}System.out.println(res);}}

这篇关于NO6---蓝桥杯JAVA---连号区间数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---