1030. 完美数列(25)

注意：数据的类型使用double类型，不然长度不够会出错。

采用双重循环去查找最大长度，如果j是从i开始查找，会出现运行超时，

优化的方法是从上一次找到的最大值的位置的下一个开始。

另外：考虑问题要全面。

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

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

输入格式：

输入第一行给出两个正整数N和p，其中N（<= 10⁵）是输入的正整数的个数，p（<= 10⁹）是给定的参数。第二行给出N个正整数，每个数不超过10⁹。

输出格式：

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

10 82 3 20 4 5 1 6 7 8 9输出样例：
8
#include "iostream"#include <algorithm>#include <vector>using namespace std;int main(){	int N = 0;	double p = 0;	vector<double> input;	double tmp = 0;	cin >> N >> p;	for (int i = 0; i < N; i++)	{		cin >> tmp;		input.push_back(tmp);	}	sort(input.begin(), input.end());	int max=0;	int index = 0;	for (int i = 0; i < N; i++)	{		for (int j = max+i; j < N; j++)		{			if (p*input[i] < input[j])			{				index = j - i;				break;			}			else if (j == N - 1)				index = j - i + 1;		}		if (max < index)			max = index;	}	cout << max << endl;;	system("pause"); 	return 0;}