蓝桥杯：连号区间数

连号区间数     小明这些天一直在思考这样一个奇怪而有趣的问题：     在1~N的某个全排列中有多少个连号区间呢？这里所说的连号区间的定义是：     如果区间[L, R] 里的所有元素（即此排列的第L个到第R个元素）递增排序后能得到一个长度为R-L+1的“连续”数列，则称这个区间连号区间。     当N很小的时候，小明可以很快地算出答案，但是当N变大的时候，问题就不是那么简单了，现在小明需要你的帮助。 输入格式： 第一行是一个正整数N (1 <= N <= 50000), 表示全排列的规模。 第二行是N个不同的数字Pi(1 <= Pi <= N)， 表示这N个数字的某一全排列。 输出格式： 输出一个整数，表示不同连号区间的数目。 示例： 用户输入： 4 3 2 4 1 程序应输出： 7 用户输入： 5 3 4 2 5 1 程序应输出： 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]

//我把这个代码粘到题里 值得了六十分  原因是运算超时 之后我将判断方法改了一下 但是改了还是超时。之后想了想每次输入后都比较出最大最小值 然后最大值减去最小值若差等于j-i 则这是连号区间，也就是将我后来改的的判断方法直接提到for循环里。

这个是60分的

import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { int count=0; Scanner s=new Scanner(System.in); int n=s.nextInt(); int a[]=new int[n]; for(int i=0;i<n;i++){ a[i]=s.nextInt(); } for(int i=0;i<n;i++){ for(int j=i;j<n;j++){ int b[]=new int[j-i+1]; for(int k=0;k<b.length;k++){ b[k]=a[k+i]; } if(judge(b)){ count++; } } } System.out.println(count); } public static boolean judge(int a[]){ Arrays.sort(a); if(a.length==1) return true; for(int i=0;i<a.length-1;i++){ if(a[i+1]-a[i]!=1) return false; } return true; } }

这是我改的判断方法：

public static boolean judge(int a[]){ if(a.length==1) return true; Arrays.sort(a); if(a[a.length-1]-a[0]==a.length-1) return true; return false; }

这是正确的方法： import java.util.Scanner; public class Main{ public static void main(String[] args) { int count=0; Scanner s=new Scanner(System.in); int n=s.nextInt(); if(n<1||n>50000)return; int a[]=new int[n]; for(int i=0;i<n;i++){ a[i]=s.nextInt(); if(a[i]<1||a[i]>n)return; } for(int i=0;i<n;i++){ int max=0,min=50001; for(int j=i;j<n;j++){ if(a[j]<min)min=a[j]; if(a[j]>max)max=a[j]; if(max-min==j-i){ count++; } } } System.out.println(count); } }