轻重搭配（贪心）

描述

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

输入

第一行整数n，表示人数；
第二行有n个整数，表示每个人的体重。

输出

最少需购买的门票数

输入样例 1

6
1 9 7 3 5 5

输出样例 1

4

#include<stdio.h>

int main(){
    
	int n;
	scanf("%d",&n);		//输入人数
	int a[100];
	int i;
	int flag[100] = {
    0};
	for(i=0;i<n;i++){
    		//输入各人体重
		scanf("%d",&a[i]);
	}
	int j,k,t;
	for(i=0;i<n;i++){
    		//升序排序 
		k = i;
		for(j=i+1;j<n;j++){
    
			if(a[j]<a[k]){
    
				k = j;
			}
		}
		if(k!=i){
    
			t = a[i];
			a[i] = a[k];
			a[k] = t;
		}
	}
	int sum=0; 
	int p=0;
	for(i=n/2;i<n;i++){
    		//从体重较重后半段开始
		if(a[i]>2*a[p]){
    
			flag[p] = 1;		//可以搭配2x体重的人
			p++;
		}
		sum++;			//两人只需买一张票
	}
	for(i=0;i<n/2;i++){
    
		if(flag[i]==0){
    		//找不到搭配的人，需另外再购票
			sum++;
		}
	} 
	printf("%d\n",sum);
}