自动搬运

查看原文

来自洛谷，原作者为

	mairuisheng 1.广州市第六中学 2.每周五回关

搬运于2025-08-24 23:14:04，当前版本为作者最后更新于2025-05-20 17:14:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目：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);
    }
}