【C语言】程序设计：轻重搭配

n 个同学去动物园参观，原本每人都需要买一张门票，但售票处推出了一个优惠活动，一个体重为 x 的人可以和体重至少为 2x配对，这样两人只需买一张票。现在给出了 n 个人的体重，请你计算他们最少需要买几张门票？ 

第一行一个整数 n，表示人数。

第二行 n 个整数，每个整数 ai​ 表示每个人的体重。

一个整数，表示最少需要购买的门票数目。

1 和 9 配对，7 和 3配对，剩下 5,5单独，一共买四张票。

6
1 9 7 3 5 5

4

为了更好的进行x与2x的配对我们需要把数组元素进行排序。（如果采用冒泡排序的话我们可以看数据范围给我们的提示 500000 该数据过于庞大，所以采用冒泡会出现超时现象正如如下代码，所以我们在这里采用快速排序）。排序完成后我们就应该考虑配对问题。

配对问题：

如果我们从第一个数开始找可以与它配对的数字，即我们可以遍历数组，但是这样操作会出现浪费问题，比如数组a={ 1， 2 ， 4， 6 }，从头开始寻找即会将 1 和 2 进行配对，这样本可以和 4 配对的 2 就被浪费掉了。

反之，如果我们从第一个数字开始从最后一个数组元素开始为它寻找配对数字也会造成浪费。

所以我们可以想出一个更好的方法：将数组元素排序后折半分开，从前半部分的最大值开始，在后半部分中遍历寻找与之配对的数字。这样就不会造成浪费。

如果我们采用冒泡排序则会出现超时现象，但是对于小数组的数值排序采用冒泡也是可以的，所以这里我提供两个代码，一个为使用冒泡排序，一个为使用快速排序。 （ 冒泡排序代码不能AC，快速排序代码可以通过）。

#include
int main()
{
	int n,i,j,t;
	scanf("%d",&n);
	int a[500005];
	for(i=0;ia[i+1])
			{
			
			    t=a[i];
				a[i]=a[i+1];
				a[i+1]=t;	
			}
		}
	}
    int count=0; //定义x与2x配对成功的票数 
    int sum;
	for(i=n/2;i>=0;i--) //折半后从前半部分最大开始与后半部分配对 
	{
	   for(j=n/2+1;j 
 正确代码 
#include
void quicksort(int left, int right)   
{
	int temp,t; 
	int n,i,j,a[500005]; 
	if(left > right) 
	{
		return;
	}
	
	temp = a[left];   
	i = left;     
	j = right;    
	while(i != j)     
	{
		while(a[j] >= temp && i= 2*a[i])
		{
			count++;//如果配对成功 票数+1
			i--;    //前半部分前移 
			j--;    //后半部分前移 
		}
    	else
		{
			i--;
		}
	}
	sum=n-2*count+count;//所需的总票数即配对成功的票数加上为配对成功的人数 
	printf("%d",sum);
			
		
	
}