PAT 1030 完美数列(25)

题目

/*
 1030. 完美数列(25)
 
 给定一个正整数数列，和正整数p，设这个数列中的最大值是M，最小值是m，如果M <= m * p，则称这个数列是完美数列。
 
 现在给定参数p和一些正整数，请你从中选择尽可能多的数构成一个完美数列。
 
 输入格式：
 
 输入第一行给出两个正整数N和p，其中N（<= 10^5）是输入的正整数的个数，p（<= 10^9）是给定的参数。第二行给出N个正整数，每个数不超过10^9。
 
 输出格式：
 
 在一行中输出最多可以选择多少个数可以用它们组成一个完美数列。
 
 输入样例：
10 8
2 3 20 4 5 1 6 7 8 9
 输出样例：
 8
 */

思路

// 考虑过程
// m[i]*p - M[j] >= 0 j-i 尽量大

// 123456789*p m  小->大
// 123456789   M

//思路： 先排序，再找最大值

代码

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main(){
	int n;
	float p;
	int seq[100005];
	int res = 1; // 这里初始化为0会造成后面数组越界，开始的算法不会有这个问题，改变算法后此处不改导致错误产生
	cin >> n >> p;
	
	
	for (int i = 0; i < n; ++i) {
		scanf("%d",&seq[i]);
	}
	
	sort(seq, seq+n);

//	 这个算法是不断缩小范围，每次都需要从最大开始进行缩小。这个算法会导致超时
//	for (int i = 0; i < n; ++i) {
//		for (int j = n-1; j > i + res - 1; --j) {
//			if (seq[j] <= product[i]) {
//				if (j - i + 1 > res) {
//					res = j - i + 1;
//				}
//				break;
//			}
//		}
//	}
	
	//	这个算法是不断扩大范围，每次扩大的范围越来越小，因为满足条件的值是在小范围内波动的。
	for (int i = 0; i < n; ++i) {
		for (int j = i+res-1; j < n;++j){
			if (seq[j] <= seq[i]*p) {
				if (j-i+1 > res) {
					res = j - i + 1;
				}
			}else{
				break;
			}
			
		}
	}
	
	printf("%d
",res);
	
	
}

过程资料

注意：

1. 纯整数运算在数据较大时容易越界导致结果错误。应当将其转化为浮点运算。在此题中即把 p 定义为浮点数。
2. 改变算法后，使用的变量的初值可能会需要改变，要对变量的边界改变情况敏感。例如此题中的res初值。

---

测试点：

1. 数组越界导致1、3测试点错误。
2. 最后一个测试点是大数，m*p 会超出整数范围，不能使用整数进行计算。