我的PAT系列文章更新重心已移至Github，欢迎来看PAT题解的小伙伴请到Github Pages浏览最新内容。此处文章目前已更新至与Github Pages同步。欢迎star我的repo。
题目
给定一个正整数数列，和正整数 ，设这个数列中的最大值是
，最小值是
，如果
，则称这个数列是完美数列。
现在给定参数 和一些正整数，请你从中选择尽可能多的数构成一个完美数列。
输入格式：
输入第一行给出两个正整数 和
，其中
（
）是输入的正整数的个数，
（
）是给定的参数。第二行给出 个正整数，每个数不超过
。
输出格式：
在一行中输出最多可以选择多少个数可以用它们组成一个完美数列。
输入样例：
10 8
2 3 20 4 5 1 6 7 8 9
输出样例：
8
思路
上了陈越、何钦铭老师的MOOC的同学（没上过也可能）应该记得一个“最大子列和”问题。陈越老师从的方案一直讲到
的方案，其实就是思路的优化。这道题有很相似的特性。
当然这道题应该没有的方案，因为这个需要排好序，所以至少是
。不过如果看排好序后的时间消耗，是可以达到
的。
- 先对数组进行非递减排序。
- 设置两个指针，分别代表完美数列的开头和结尾。
- 每次我们都将结尾指向刚刚开始大于开头的一个数，二者距离就是目前完美数列的最长长度。
- 开头指针向下进行遍历，这个时候结尾指针只需从原位置开始向下遍历即可，因为新的开头的数一定更大，那么结尾的数一定不会小于上次的值。
这样我们所用的时间就是开头和结尾分别一次遍历的时间，就是2N，完成的目标。
代码实现：
题目给的数字都是小于 的，但是在判断
的时候，
是可能大于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;
}
