[PAT解题报告]完美数列(25)
import java.util.Collections; import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner input=new Scanner(System.in); int n=input.nextInt(); int p=input.nextInt(); int count=0; int []array=new int[n]; for (int i = 0; i < n; i++) { array[i]=input.nextInt(); } quickSort(array, 0, n-1); for (int i = 0; i < n; i++) { count=(search(array, p*array[i])-i>count)?search(array, p*array[i])-i:count; if((array.length-i)<count) { break; } } System.out.println(count+1); } public static void quickSort(int[] a, int lo0, int hi0) { int lo = lo0; int hi = hi0; if (lo >= hi) return; boolean tran敏感词er=true; while (lo != hi) { if (a[lo] > a[hi]) { int temp = a[lo]; a[lo] = a[hi]; a[hi] = temp; tran敏感词er = (tran敏感词er == true) ? false : true; } if(tran敏感词er) hi--; else lo++; } lo--; hi++; quickSort(a, lo0, lo); quickSort(a, hi, hi0); } public static int search(int[] number, int des) { int low = 0; int upper = number.length - 1; while (low <= upper) { int mid = (low + upper) / 2; if (mid+1>number.length - 1) { return number.length - 1; } if ((number[mid] <= des)&&(number[mid+1] <= des)) low = mid + 1; else if (number[mid] > des&&number[mid+1] > des) upper = mid - 1; else if (number[mid] <= des&&number[mid+1] >= des) return mid; } return -1; } }