16蓝桥杯算法训练—区间k大数查询

import java.util.Scanner; /*区间k大数查询  : 问题描述 给定一个序列，每次询问序列中第l个数到第r个数中第K大的数是哪个。 输入格式 第一行包含一个数n，表示序列长度。 第二行包含n个正整数，表示给定的序列。 第三个包含一个正整数m，表示询问个数。 接下来m行，每行三个数l,r,K，表示询问序列从左往右第l个数到第r个数中，从大往小第K大的数是哪个。序列元素从1开始标号。 输出格式 总共输出m行，每行一个数，表示询问的答案。 样例输入 5 1 2 3 4 5 2 1 5 2 2 3 2 样例输出 4 2 数据规模与约定 对于30%的数据，n,m<=100； 对于100%的数据，n,m<=1000； 保证k<=(r-l+1)，序列中的数<=106。 */ public class BigNum_Found  { public static void main(String[] args)  { //输入第一行n Scanner s1 = new Scanner(System.in); int n = s1.nextInt(); if(n<=1000) { //第二行数列赋值 Scanner s2 = new Scanner(System.in); Scanner s3 = new Scanner(s2.nextLine()); int arr1[] = new int[n]; int i=0; while(s3.hasNext()) { arr1[i] = s3.nextInt(); i++; } //排序数列,从大到小 for(int j=0; j<n; j++) { for(int k=1; k<n; k++) { if(arr1[k]>arr1[k-1]) { int flag = arr1[k]; arr1[k] = arr1[k-1]; arr1[k-1] = flag; } } } //输入第三行m Scanner s4 = new Scanner(System.in); int m = s4.nextInt(); int arr3[] = new int[m]; //储存最后结果的数组 int mm=0; //arr3增长的标志 if(m<=1000) { double mn = m/n; if(mn == 0.3) if(n>100 || m>100) return; //第四行l,r,k for(int j=0; j<m; j++) { Scanner s5 = new Scanner(System.in); Scanner s6 = new Scanner(s5.nextLine()); int arr2[] = new int[3]; //存储每次输入的 l,r,k int a=0; while(s6.hasNext()) { arr2[a] = s6.nextInt(); a++; } int l=arr2[0]; int r=arr2[1]; int k=arr2[2]; //找数 if(k<=(r-l+1) && k<=106 && l<=106 && r<=106) { int flag1=0,flag2=0,flag3=1; //找出l到r 在arr1数列中的数列段 for(int ii=0; ii<arr1.length; ii++) { if(arr1[ii] == r) flag1 = arr1[ii]; if(arr1[ii] == l) flag2 = arr1[ii]; } //在该数列段中找K, flag3作为该数排行的标记 for(int ii=flag2; ii<flag1; ii++) { flag3++; if(arr1[ii] == k) { break; } } arr3[mm] = flag3;   mm++; } } //结果输出 for(int ii=0; ii<arr3.length; ii++) { System.out.println(arr3[ii]); } } } } }