题目

时间限制
300 ms
内存限制
65536 kB
代码长度限制
8000 B
判题程序
Standard
作者
CAO, Peng
给定一个正整数数列，和正整数p，设这个数列中的最大值是M，最小值是m，如果M <= m * p，则称这个数列是完美数列。
现在给定参数p和一些正整数，请你从中选择尽可能多的数构成一个完美数列。
输入格式：
输入第一行给出两个正整数N和p，其中N（<=

10 8
2 3 20 4 5 1 6 7 8 9

输出样例：

8

分析：

读懂题意，比如对于1 3 5 4 2 这样的数组，当p为2时，从
最小值1开始，1*2<=2，此时长度为2，即1 2
最小值2开始，2*2<=4，此时长度为3，即2 3 4
最小值3开始，3*2<=6，此时长度为3，即3 4 5
最小值4时，数组长度为2，不可能更大了，所以该数组在p为2的情况下，组成完美数组的最多数是3个。
我们开始分析步骤：
1.排序，排序原因是数为有序的情况下，最大值最小值之间的值肯定是满足条件的
2.从数组第一个数为最小数，再次从后一个开始查找满足条件的最大值，当不满足条件时break内层循环
为了简化时间复杂度，由于每次能找出当前最多数，所以查找可以以第一个数为最小数，最小数+最多数为开始查找的最大数

代码（cpp）

#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    long n,p;
    long a[100000+5];
    int num=0;
    cin>>n>>p;
    for(int i=0;i<n;i++)
        cin>>a[i];
    sort(a,a+n);  //默认升序
    for(int i=0;i<n;i++)
        for(int j=i+num;j<n;j++){
            if(a[i]*p<a[j])
                break;
            if(num < j-i+1)
                num =j-i+1;
        }
    cout<<num;
    return 0;
}

PAT.1030. 完美数列

题目

分析：

代码（cpp）