题解：P12257 [蓝桥杯 2024 国 Java B] 分组

· · 题解

题目：P12257 [蓝桥杯 2024 国 Java B] 分组

主要算法：贪心，双指针。

分析：

首先，判无解情况：分数中最大值小于分数中最小值的两倍一定不行，输出 0，结束程序。

否则用双指针求解：如果每组分两个同学，得到的是最优方案（剩下的同学可以分其他组）。所以先把数组 a 排序，设左指针 l 和右指针 r。如果 a_r\ge a_l\times 2，标记两个指针的位置，表示这两个同学已经被分组了；否则左指针前移，寻找下一个同学。

注意事项：考虑到最多分 \frac{2}{n} 组，所以 l 的初值为 \frac{2}{n}。

以下代码用位运算优化乘除法。

C++ 代码：

#include<cstdio>
#include<algorithm>
#include<bitset>
using namespace std;
inline int read()
{
    int x=0,f=1;
    char s;
    s=getchar();
    while(s<48||s>57)
    {
        if(s=='-')f=-f;
        s=getchar();
    }
    while(s>47&&s<58)
    {
        x=(x<<3)+(x<<1)+s-48;
        s=getchar();
    }
    return x*f;
}
constexpr int N=1e5+1;
int n;
int a[N];
int maxn,minn=1e8;
bitset<N> vis;
int ans;
int main()
{
    n=read();
    int i;
    for(i=1;i<=n;++i)
    {
        a[i]=read();
        maxn=max(maxn,a[i]);
        minn=min(minn,a[i]);
    }
    if(minn*2>maxn)//特判。
    {
        putchar('0');
        return 0;
    }
    sort(a+1,a+1+n);
    int l=n>>1,r=n;//双指针。
    while(l>0)
    {
        if((a[l]<<1)>a[r])--l;
        else
        {
            ++ans;
            vis[l]=true;
            vis[r]=true;
            --l,--r;
            while(r>0&&vis[r])--r;
        }
    }
    printf("%d",ans);
    return 0;
}

Java 代码：

import java.util.Arrays;
import java.util.BitSet;
import java.util.Scanner;

public class Main
{
    static final int N=100001;
    static int n;
    static int[] a=new int[N];
    static int maxn, minn=(int)1e8;
    static BitSet vis=new BitSet(N);
    static int ans;

    public static void main(String[] args)
    {
        Scanner scanner=new Scanner(System.in);
        n=scanner.nextInt();

        for(int i=1;i<=n;++i)
        {
            a[i]=scanner.nextInt();
            maxn=Math.max(maxn,a[i]);
            minn=Math.min(minn,a[i]);
        }

        if((minn<<1)>maxn)//特判。
        {
            System.out.print(0);
            return;
        }

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

        int l=n>>1,r=n;//双指针。
        while(l>0)
        {
            if((a[l]<<1)>a[r])--l;
            else
            {
                ++ans;
                vis.set(l);
                vis.set(r);
                --l;
                --r;
                while(r>0 &&vis.get(r))--r;
            }
        }
        System.out.print(ans);
    }
}