PATAdvanceLevel（甲级）1085

发表于 更新于 分类于 ， 本文字数： 2.3k 阅读时长 ≈ 2 分钟

题目链接：1085 Perfect Sequence (25分)

题目描述如下：

作者 CAO, Peng
单位 浙江大学
代码长度限制 16 KB
时间限制 200 ms
内存限制 64 MB
1085 Perfect Sequence (25分)
Given a sequence of positive integers and another positive integer p. The sequence is said to be a perfect sequence if M≤m×p where M and m are the maximum and minimum numbers in the sequence, respectively.

Now given a sequence and a parameter p, you are supposed to find from the sequence as many numbers as possible to form a perfect subsequence.

Input Specification:
Each input file contains one test case. For each case, the first line contains two positive integers N and p, where N (≤10^5) is the number of integers in the sequence, and p (≤10^9) is the parameter. In the second line there are N positive integers, each is no greater than 10^9.
Output Specification:
For each test case, print in one line the maximum number of integers that can be chosen to form a perfect subsequence.
Sample Input:
10 8
2 3 20 4 5 1 6 7 8 9

Sample Output:
8

题目大意：

完美序列 ：序列的最大值为M，最小值为m，给定一个p值，满足M≤m*p的序列称为完美序列。
求出给定序列中能组成完美序列的最大可能的元素个数。

输入
输入序列中的整数个数N，给定元素p和N个整数。
输出
能组成完美序列的最大元素个数。

解题思路：

本题主要的思路就是从给定的序列中找出尽量多的数组成完美序列，不过需要注意的组成完美序列的数不必按给定序列的顺序。
本题的解法应该有很多，本人的解法如下：
1、先对输入序列进行排序
2、以最小的数作为完美序列的最小值，求出此时能组成完美序列的元素个数和第一个不满足完美序列的数的下标，因为此时的序列有可能不是最大的。
3、求出能满足刚才找出元素的最小值下标，以此为新的完美序列的最小值求出此时的最大元素个数，若此时序列长度大于刚才的长度则更新长度值，一直重复直到序列末尾。

注意采用暴力穷举的方法会超时

本题的C/C++代码如下所示
代码如下：

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#pragma warning(disable:4996)；
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string>
#include<string.h>
#include<math.h>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<limits.h>
#define Max 101000

using namespace std;

/*判断是否满足完美序列的定义*/
bool check(long long M, long long m, long long p)
{
	return M <= m*p;
}

int main(void)
{
	long long n, p;
	cin >> n >> p;
	long long total = 0;
	long long a[Max] = { 0 };

	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}

	sort(a, a + n);//对给定序列进行排序
	int i = 0, j = 0;//i为最小值坐标，j为最大值坐标

	/*最大值坐标的界限为序列的最后一个元素，最小值的界限为序列长度-以求出完美序列长度，
	因为此坐标后的元素作为最小值即使后面的数全部满足完美序列的定义也不可能超过已知完美序列的长度*/
	for (; j < n&&i<n - total; )
	{
		/*求出以坐标为i的元素为最小值的完美序列长度*/
		while (check(a[j], a[i], p) && j < n)
		{
			if (j - i + 1>total)
			{
				total = j - i + 1;
			}
			j++;
		}
		/*找出下一个满足完美序列最小值的下标*/
		while (!check(a[j], a[i], p) && i<n - total)
		{
			i++;
		}
	}
	cout << total << endl;

	system("pause");

	return 0;
}

总结

理解了完美序列的定义和题目的意思就能很快的做出此题。

谢谢阅读，希望对你有所收获。