题目描述

给定一个正整数数列，和正整数p，设这个数列中的最大值是M，最小值是m，如果M <= m * p，则称这个数列是完美数列。
现在给定参数p和一些正整数，请你从中选择尽可能多的数构成一个完美数列。

输入描述

输入第一行给出两个正整数N和p，其中N（<= 10⁵）是输入的正整数的个数，p（<= 10⁹）是给定的参数。第二行给出N个正整数，每个数不超过10⁹。

输出描述

在一行中输出最多可以选择多少个数可以用它们组成一个完美数列。

输入例子

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

输出例子

8

我的代码

//代码没通过
#include<stdio.h> 
int main(){
    int n,i,j,t;
    long p,a[100000],min;
    scanf("%d %ld",&n,&p);
    for(i=0;i<n;i++){
        scanf("%ld",&a[i]);
    }
    for(i=0;i<n-1;i++){     //排序过于耗时间 
        for(j=i+1;j<n;j++){
            if(a[i]>a[j]){
                t=a[i];
                a[i]=a[j];
                a[j]=t;
            }
        }
    }
    min=a[0];
    for(i=1;i<n;i++){
        if(a[i]<=min*p){
            continue;
        }
        else{
            printf("%d",i);
            break;
        }
    }
    return 0;
}

我的分析

我的代码没通过的原因是超时。我写这道题的思路是将它所给的一系列数按照从小到大来排序，然后就知道了最小的那一个数，之后再在排好序的数组之中一个一个测试M<=m*p是否成立，找到最小的一个不成立的，则i就是所需要的答案。但是题目中可能会给出很多很多的数字，那么我这里的排序可能会花费相当大的时间（因为还没有学数据结构，现在只会冒泡排序），所以无法通过，等我之后学习了更高效的排序后再回来重新编写。

正确代码

//思路不同的代码
#include<stdio.h>
int main(){
    int n,m,i,t=0;
    long a[100000],p,max=0,min;
    scanf("%d %ld",&n,&p);
    for(i=0;i<n;i++){
        scanf("%ld",&a[i]);
        if(a[i]>max){    //在输入的时候先找出最大的数，减少时间
            max=a[i];
        }
    }
    if(max%p!=0){       //再找出能够满足的最小的数
        min=(max/p)+1;
    }
    else{
        min=max/p;
    }
    for(i=0;i<n;i++){
        if(a[i]<min){
            t++;       //开始计数
        }
    }
    if(p==2){         //p=2时的特殊情况
        printf("%ld",n-t+3);
    }
    else{
        printf("%d",n-t);   
    }
    return 0;
}