PAT (Basic Level) Practise （中文）-1030. 完美数列(25) http://www.patest.cn/contests/pat-b-practise/1030
给定一个正整数数列，和正整数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. 一个正整数数列，最大值是M，最小值是m，如果M <= m * p，则称这个数列是完美数列。
2. 给出一组正整数，但是无序。
为了检测M <= m * p，需要得出最大值和最小值；
为了得出最大值和最小值中间存在多少个数据，则需要知道大于等于最小值且小于等于最大值的数据有多少个。为了简化，则需要排序。
3. 10的5次方个数据，数据量大，则必须选择高效的排序算法；数值为（0，10的九次方]，最大值太高，则无法使用hash。
4. 求最长的完美数列，而原数列已经有序。则如同两个人拉个绳子，一个站在某个数据处，另一个走向远方，直到走到不再满足完美数列时，则停止。这个绳子的长度，就是这个完美数列的长度。
输出格式：
在一行中输出最多可以选择多少个数可以用它们组成一个完美数列。
#include<stdio.h> void QS(long long *num,int low,int high)
{
long long temp=num[low];
int l=low,h=high;
while(l<h)
{
while(num[h]>=temp && h>l)
h--;
if(num[h]<temp)
{
num[l]=num[h];
num[h]=temp;
l++;
} while(num[l]<=temp && l<h)
l++;
if(num[l]>temp)
{
num[h]=num[l];
num[l]=temp;
h-- ;
}
}
if(l->low) QS(num,low,l-);
if(h+<high)QS(num,h+,high); return;
} int main()
{
int n=;
long long p=;
scanf("%d%lld",&n,&p); long long num[]={};
for(int i=;i<n;i++)
scanf("%lld",&num[i]); if(n==)
{
if(num[]<=num[]*p)
printf("");
else
printf("");
return ;
} QS(num,,n-);
int diff=,min=,max=;
while(n-min>=diff)
{
while(num[max]<=num[min]*p )
{
max++;
if(max==n) break;
}
if(max-min>diff)
diff=max-min;
if(max==n) break;
if(min<n-) min++;
}
printf("%d",diff);
return ;
}