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

题目

给定一个正整数数列，和正整数p，设这个数列中的最大值是M，最小值是m，如果M <= m * p，则称这个数列是完美数列。
现在给定参数p和一些正整数，请你从中选择尽可能多的数构成一个完美数列。

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

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

输入样例：

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

输出样例：

8
1

来源：PAT 1030 完美数列
——————————————————————

思路（注意事项）

1. a[i]*p可能会超过int所能表示范围，所以定义用long long。

2. sort(a, a + n); 指的是将a[0]~a[n-1]的数组元素进行排序
   sort（first,last） first 和 last 是迭代器，表示要排序的范围。 注意，last 指向的是范围末尾的下一个位置，不包含在排序范围内。 （需要头文件algorithm）

3. 本题难点，双层循环中，第二层循环的编写，利用之前计算得到的 max_cont 来减少不必要的比较，从而优化性能。

——————————————————————

题解

#include<iostream>
#include<algorithm>
#include<cmath>
#define rep(i , a , n) for(int i = a; i < n; i++)
using namespace std;
int main()
{
	int n, max_cont = 1;//max_cout为完美数列的个数 
	long long p;
		cin >> n >> p;
	long long a[n];//a[i]*p可能会超过int所能表示范围
	rep(i, 0, n)
		cin >> a[i];
	sort(a, a + n);//对传入的所有数进行排序 
	rep(i, 0, n) //外层循环遍历数组 a 的每一个元素，作为子序列的起始位置,也即最小值
	{
		rep(j,i + max_cont, n) //从当前起始位置 i 加上当前已知的最大连续长度 max_cont 开始，遍历数组。
		{
			if(a[j] <= a[i] * p)  //满足，则更新 max_cont 为当前子序列的长度 j - i + 1
				max_cont = j - i + 1;
			else  //不满足，则跳出内层循环，因为后续的元素只会更大
				break;
		}
	}
	cout << max_cont;//输出构成完美数列的数的个数 
	return 0;
}