PAT Basic 1030. 完美数列(25)（C语言实现）

我的PAT系列文章更新重心已移至Github，欢迎来看PAT题解的小伙伴请到Github Pages浏览最新内容。此处文章目前已更新至与Github Pages同步。欢迎star我的repo。

题目

给定一个正整数数列，和正整数 $p$ ，设这个数列中的最大值是 $M$ ，最小值是 $m$ ，如果 $M \le mp$ ，则称这个数列是完美数列。

现在给定参数 $p$ 和一些正整数，请你从中选择尽可能多的数构成一个完美数列。

输入格式：

输入第一行给出两个正整数 $N$ 和 $p$ ，其中 $N$ （ $\le 10^5$ ）是输入的正整数的个数， $p$ （ $\le 10^9$
）是给定的参数。第二行给出 $N$ 个正整数，每个数不超过 $10^9$ 。

输出格式：

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

输入样例：

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

输出样例：

思路

上了陈越、何钦铭老师的MOOC的同学（没上过也可能）应该记得一个“最大子列和”问题。陈越老师从 $O(N^3)$ 的方案一直讲到 $O(N)$ 的方案，其实就是思路的优化。这道题有很相似的特性。
当然这道题应该没有 $O(N)$ 的方案，因为这个需要排好序，所以至少是 $O(N \log{N})$ 。不过如果看排好序后的时间消耗，是可以达到 $O(N)$ 的。

先对数组进行非递减排序。
设置两个指针，分别代表完美数列的开头和结尾。
每次我们都将结尾指向刚刚开始大于开头的一个数，二者距离就是目前完美数列的最长长度。
开头指针向下进行遍历，这个时候结尾指针只需从原位置开始向下遍历即可，因为新的开头的数一定更大，那么结尾的数一定不会小于上次的值。

这样我们所用的时间就是开头和结尾分别一次遍历的时间，就是2N，完成 $O(N)$ 的目标。

代码实现：

题目给的数字都是小于 $10^9$ 的，但是在判断 $M \le m p$ 的时候， $m p$ 是可能大于32位整型范围的，要合理处理这个数字。

代码

最新代码@github，欢迎交流

#include <stdio.h>
#include <stdlib.h>

int comp(const void *a, const void *b)
{
    return *(int*)a - *(int*)b;
}

int main()
{
    int N, p, data[100000];
    int max = 0, first, last;

    scanf("%d %d", &N, &p);                                         /* read */
    for(int i = 0; i < N; i++)
        scanf("%d", data + i);

    qsort(data, N, sizeof(int), comp);                              /* sort */

    for(first = 0, last = 0; last < N && max < N - first; first++)  /* find */
    {
        while(last < N && data[last] <= 1L * data[first] * p)
            last++;
        if(max < last - first)
            max = last - first;
    }
    printf("%d", max);

    return 0;
}