题目

https://www.luogu.com.cn/problem/P12257

思路

把同学们分为尽可能多的小组，考虑贪心。小组内的人数越少，组数也就越多。自然地一个想法是尽可能两人一组 {Min, Max} ，其中 Max >= Min*2。
理想情况下，最多可以分为 n/2（向下取整） 个小组。当总人数为奇数的时候，一定会存在三人组，因为单人不能成为一组。

用最大的数去匹配尽可能大的、满足条件的小数，是一个非常靠谱的贪心策略。所以先对数组排序。

由于最多能有 n/2 个小组，一个自然的分界线是数组的中间，将数组划分为左半部分的“小数池”，与右半部分的“大数池”。
基于 1 的索引，左指针初始化下取整l = n/2：当数组为偶数个元素，那么划分出的小数池和划分出的大数池的个数是相等的；当数组为奇数个元素，那么划分出的小数池元素个数 < 大数池的元素个数。
再加上代码中 l 移动的次数一定大于等于 r 移动的次数，这样就保证了 l 和 r 的移动过的路径一定不会重叠。

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

const int N = 100010;
int n;
int a[N];

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++)
        scanf("%d", &a[i]);

    sort(a+1,a+n+1);

    if(a[1]*2 > a[n])
    {
        printf("0");
        return 0;
    }

    int l = n/2, r = n; //l初始化为下取整
    int res = 0;
    while(l > 0) //设置l为循环边界
    {
        if(a[l]*2 > a[r]) //不能组一块
            l--;
        else
        {
            res++;
            l--; r--; //所以l一定比r减的次数多，r一定是够用的
        }
    }
    printf("%d",res);
    return 0;
}

分组最多的方案一定是由若干个两人小组和一些无法配对的单人组成的。其中无法配对的元素可以加入到最小值那一组，不会影响组内的最大值和最小值。