完美数列(PAT)

1.题目描述

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

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

2.输入描述:

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

3.输出描述:

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

4.输入例子:

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

5.输出例子:

8

6.解题思路

一、对于一个数列，要想从中知道最大长度的完美数列，根据题目所给出的公式，首先我们想到的应该是先将整体数列进行排序，然后从中找出规律。
二、注意点：排序要用快速排序更快，起初用简单冒泡直接超时了；为了避免出现段错误，我们需要直接定义一个100000的数组，而不用分配内存的方法，因为在后面优化过程中会出现访问大于N的数组空间。
三、优化点：
1.因为最大值只可能在第i个数的后面，所以最大值只能在i后面遍历，即j=i。
2.因为count是完美数列的最大长度，如果当i向后移动，则没必要再判断小于count长度的数列是否符合完美数列，即j=i+count。例如当count=2，i=2的时候，我们就没必要考虑，j=2、3的情况，因为数列【2】和【2,3】小于等于最大的完美数列长度
如图：

7. 源代码：

#include<stdio.h>
void qsort(int num[],int L,int R)//快速排序 
{
	if(L<R)
	{
		int i=L;
		int j=R;
		int k=num[L];
		while(i<j)
		{
			while(i<j&&num[j]>=k)
				j--;
			if(i<j)
				num[i++]=num[j];
			while(i<j&&num[i]<k)
				i++;
			if(i<j)
				num[j--]=num[i];
		}
		num[i]=k;
		qsort(num,L,i-1);
		qsort(num,i+1,R);
	}
}
int main()
{
	double p;
	int i,j,N,num[100000],count=0;
	scanf("%d %lf",&N,&p);
	for(i=0;i<N;i++)
		scanf("%d",&num[i]);
	qsort(num,0,N-1);
	for(i=0;i<N;i++)
		for(j=i+count;j<N;j++)
		{
			if(num[j]>num[i]*p)
				break;
			count++;
		}
	printf("%d",count);
	return 0;
}