计蒜客：2019 蓝桥杯省赛 B 组模拟赛（一）程序设计：轻重搭配（贪心）

桃扇骨 2022-02-28 00:04 203阅读 0赞

#                                 程序设计：轻重搭配 #

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

### 输入格式 ###

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

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

### 输出格式 ###

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

### 数据范围 ###

对于 30% 的数据：1≤n≤25，1≤ai≤100。

对于 60% 的数据：1≤n≤10000，1≤ai≤1000。

对于 100% 的数据：1≤n≤5⋅10^5，1≤ai≤10^5。

### 样例解释 ###

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

### 样例输入 ###

6
    1 9 7 3 5 5

### 样例输出 ###

### 解题思路： ###

此题为贪心，先升序排列，i指向中间数据，j从尾开始查。若符合都向前走，不符合i向前，j不动。

### 程序代码： ###

#include<stdio.h>
    #include<algorithm>
    using namespace std;
    int main()
    {
    	int n,i,a[500050],num,j,ans;
    	while(scanf("%d",&n)!=EOF)
    	{
    		num=0;
    		ans=0;
    		for(i=1;i<=n;i++)
    			scanf("%d",&a[i]);
    		sort(a+1,a+n+1);
    		i=n/2;
    		j=n;
    		while(i)
    		{
    			if(a[i]*2<=a[j])
    			{
    				num++;
    				i--;
    				j--;
    			}
    			else
    			{
    				ans++;
    				i--;
    			}
    		}
    		printf("%d\n",num+ans+j-n/2);
    	}
    	return 0;
    }