题目

给定一个正整数数列，和正整数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>
#include <stdlib.h>
#include <stdbool.h>

int cmp(const void *first, const void *second)
{ return *(int *)first - *(int *)second; }

//这里计算可能溢出，让我想了很久才想到
bool valid(int m, int M, int p)
{ return M <= m * (long long)p; }

int perfect(const int *a, int size, int p)
{
    int max = size ? 1 : 0; //size大于0的话，至少可选一个

    for (int i = 0; i < size; ++i) {
        //只有在下一次长度超过max时，计算才有意义，所以j = i + max
        for (int j = i + max; j < size; ++j) {
            if (!valid(a[i], a[j], p)) {
                break;
            }
            else {
                max = j - i + 1;
            }
        }
    }

    return max;
}

int main(void)
{
    int n, p;
    int *a;

    scanf("%d%d", &n, &p);
    a = malloc(sizeof(int) * n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", a + i);
    }
    //从小到大排序
    qsort(a, n, sizeof(int), cmp);
    printf("%d", perfect(a, n, p));
    putchar('\n');
    
    return 0;
}