PAT乙级——1030
题目:完美数列 (25 分)
给定一个正整数数列,和正整数 p,设这个数列中的最大值是 M,最小值是 m,如果 M≤mp,则称这个数列是完美数列。
现在给定参数 p 和一些正整数,请你从中选择尽可能多的数构成一个完美数列。
输入格式:
输入第一行给出两个正整数 N 和 p,其中 N(≤105 )是输入的正整数的个数,p(≤109 )是给定的参数。第二行给出 N 个正整数,每个数不超过 109 。
输出格式:
在一行中输出最多可以选择多少个数可以用它们组成一个完美数列。
输入样例:
10 8
2 3 20 4 5 1 6 7 8 9
输出样例:
8
题目分析及实现
首先,可以想到的是将数据存储后,从小到大排序,题目知,要求队列的最长数据,需要最大值和最小值,则可以循环从头和尾获取数据,判断是否符合标准,符合则记录下数据个数,每一次判断符合都与整个数据比较,最后输出最大值。
具体大概就是两个循环,第一个循环依次向后遍历。第二个循环从第一次循环遍历位置开始,从后向前匹配。比较出最大的队列长度。
//倒数第二个用例超时,求求老天爷,求求PAT组织,对java友好一点,22分![在这里插入图片描述](https://img-blog.****img.cn/20181106205920284.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3F1bnF1bnN0eWxlOTk=,size_16,color_FFFFFF,t_70)
import java.util.Arrays;
import java.util.Scanner;
public class Y1030 {
public static void main(String[] args) {
Scanner in =new Scanner(System.in);
int N=in.nextInt();
int p=in.nextInt();
long num[]=new long[N];
for(int i=0;i<N;i++) {
num[i]=in.nextLong();
}
in.close();
int max=0;//最多数值数
int count=0;//统计个数
Arrays.sort(num);//将数组排序,从小到大
for(int i=0;i<N;i++) {
if(max>N-i+1)
break;//当max已经大于未遍历的数组时,则可以放弃
for(int j=i;j<N;j++) {
if(max>N-j+1)
break;//当max已经大于未遍历的数组时,则可以放弃
int temp=N-1;//最大值M坐标
if(num[i]*p<num[temp])
temp--;
else
if(max<temp-j+1)
max=temp-j+1;
}
}
System.out.print(max);
}
}