蓝桥杯省赛真题2013年第四届Java本科B组第10题——连号区间数

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

在1~N的某个全排列中有多少个连号区间呢&＃xff1f;这里所说的连号区间的定义是&＃xff1a;

如果区间[L, R] 里的所有元素&＃xff08;即此排列的第L个到第R个元素&＃xff09;递增排序后能得到一个长度为R-L&＃43;1的“连续”数列&＃xff0c;则称这个区间连号区间。

当N很小的时候&＃xff0c;小明可以很快地算出答案&＃xff0c;但是当N变大的时候&＃xff0c;问题就不是那么简单了&＃xff0c;现在小明需要你的帮助。

输入格式&＃xff1a;
第一行是一个正整数N (1 <&＃61; N <&＃61; 50000), 表示全排列的规模。
第二行是N个不同的数字Pi(1 <&＃61; Pi <&＃61; N)&＃xff0c; 表示这N个数字的某一全排列。

输出格式&＃xff1a;
输出一个整数&＃xff0c;表示不同连号区间的数目。

示例&＃xff1a;
用户输入&＃xff1a;
4
3 2 4 1

程序应输出&＃xff1a;
7

用户输入&＃xff1a;
5
3 4 2 5 1

程序应输出&＃xff1a;
9

解释&＃xff1a;
第一个用例中&＃xff0c;有7个连号区间分别是&＃xff1a;[1,1], [1,2], [1,3], [1,4], [2,2], [3,3], [4,4]
第二个用例中&＃xff0c;有9个连号区间分别是&＃xff1a;[1,1], [1,2], [1,3], [1,4], [1,5], [2,2], [3,3], [4,4], [5,5]

资源约定&＃xff1a;
峰值内存消耗&＃xff08;含虚拟机&＃xff09; <64M
CPU消耗 <5000ms

请严格按要求输出&＃xff0c;不要画蛇添足地打印类似&＃xff1a;“请您输入…” 的多余内容。

所有代码放在同一个源文件中&＃xff0c;调试通过后&＃xff0c;拷贝提交该源码。
注意&＃xff1a;不要使用package语句。不要使用jdk1.6及以上版本的特性。
注意&＃xff1a;主类的名字必须是&＃xff1a;Main&＃xff0c;否则按无效代码处理。

思路

题目写的比较复杂&＃xff0c;其实就是获取一个输入&＃xff0c;用来定义数组大小&＃xff0c;再接收数组元素&＃xff0c;然后截取数组&＃xff0c;截取的子数组只要递增排列后是连续的就满足条件

代码

import java.util.Arrays;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner &＃61; new Scanner(System.in);int N &＃61; scanner.nextInt();int[] nums01 &＃61; new int[N&＃43;1]; //这里为了方便&＃xff0c;多占一个空间&＃xff0c;让下标从1开始存储int count &＃61; 0; //统计个数for (int i &＃61; 1; i < nums01.length; i&＃43;&＃43;) {nums01[i] &＃61; scanner.nextInt();}for (int L &＃61; 1; L < nums01.length; L&＃43;&＃43;) {for (int R &＃61; L; R < nums01.length; R&＃43;&＃43;) {int[] nums02 &＃61; Arrays.copyOfRange(nums01, L, R&＃43;1); //截取数组放到新数组里Arrays.sort(nums02); //递增排序if (check(nums02)) { //满足连续条件则计数器&＃43;1count&＃43;&＃43;;}}}System.out.println(count);}//检查是否连续private static boolean check(int[] nums) {for (int i &＃61; 1; i < nums.length; i&＃43;&＃43;) {if (nums[i] - nums[i-1]!&＃61;1) {return false;}}return true;}
}

评测结果最后一个点超时

代码优化

第一次的代码里有排序&＃xff0c;这应该是超时的原因&＃xff0c;我们同过寻找规律可以发现&＃xff0c;不排序也可以判断区间是否连续&＃xff0c;题目里给的数都不会重复&＃xff0c;所以如果是递增的数列&＃xff0c;则最大的数-最小的数&＃43;1&＃61;数列的长度。我们在每次都更新一下最大值和最小值即可

import java.util.Arrays;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner &＃61; new Scanner(System.in);int N &＃61; scanner.nextInt();int[] nums01 &＃61; new int[N&＃43;1]; //这里为了方便&＃xff0c;多占一个空间&＃xff0c;让下标从1开始存储int count &＃61; 0; //统计个数for (int i &＃61; 1; i < nums01.length; i&＃43;&＃43;) {nums01[i] &＃61; scanner.nextInt();}for (int L &＃61; 1; L < nums01.length; L&＃43;&＃43;) {//记录截取的数组中的最大值和最小值int max &＃61; nums01[L];int min &＃61; nums01[L];for (int R &＃61; L; R < nums01.length; R&＃43;&＃43;) {if (L&＃61;&＃61;R) { //左右两个边界相等的时候&＃xff0c;只有一个数必定满足条件count&＃43;&＃43;;}else {//更新最大值和最小值if(nums01[R]>max) max&＃61;nums01[R];if(nums01[R]<min) min&＃61;nums01[R];//这里的条件&＃xff1a;如果是递增的数列&＃xff0c;则最大的数-最小的数&＃43;1&＃61;数列的长度if (max-min&＃43;1&＃61;&＃61;R-L&＃43;1) { //满足连续条件则计数器&＃43;1count&＃43;&＃43;;}}}}System.out.println(count);}}

再次测评通过