B - 程序设计：轻重搭配

B - 程序设计：轻重搭配

样例：

输入样例：
6
1 9 7 3 5 5
输出样例：
4

思路：

利用快排先将输入的体重按从小到大的顺序排列好，然后在分为两部分，从最右边和中间依次想成比较，算出需要多少张票

代码实现：

#include 
#include 
#define MAX 500005

int n,i,j;
int a[MAX];
void quicksort(int left, int right){
	int temp,t;   //temp变量是基准，t变量是用来交换的第三变量 
	if(left>right){
		return;
	}
	temp = a[left];   //此时选用的是第一个数当做基准 
	i = left;     //i是1 
	j = right;     //j是n 
	while(i != j) {
		while(a[j]>=temp&&i= 1 && r >= n/2){ //结束循环的条件 
		if(2*a[m]<=a[r]){  //判断是否大于二倍 
			sum+=1;  //满足的次数 
			m--; //依次往前一个一个算 
			r--;
		}else{
			m--;  //如果不满足，则中间的一直往前寻找 
		}
	}
	printf("%d",n-sum);  //最后总共的票数 
	return 0;
}

运行结果：