题目

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

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

输入格式：

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

输出格式：

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

输入样例：

1
2

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

输出样例：

1

8

思路

上了陈越、何钦铭老师的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最新代码，欢迎交流

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#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 = 0, last = 0;

	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 (; 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;
}