题解

思路概述

• 设我们挑选了若干组中的 A 灯泡和若干组中的 B 灯泡。无论系统最终点亮哪一侧，收益都是“被点亮的灯泡权值和”减去“总共挑选的灯泡数”。我们希望在最坏情况下也最大化收益，因此要让两侧的收益尽量平衡。
• 把所有 A 的权值按降序排列、B 的权值也按降序排列。枚举挑选的 A 灯泡数量 $i$，则最优策略显然是拿前 $i$ 个 A；与此同时，为了不让“系统点亮 B”这一侧成为短板，需要尽量补上一些高权值的 B，使得 $B$ 侧的收益至少不低于 $A$ 侧。
• 因此维护一个指针 pos 表示当前拿了多少个 B 灯泡，并维护两侧的权值和 SA、SB。每次枚举新的 $i$ 时，先更新 SA，再不断增加 pos 直到 SB ≥ SA（或者 B 被取完），这样可以保证在当前 $i`$ 下最坏收益被最大化。最后答案是所有状态下 min(SA - (i+pos), SB - (i+pos)) 的最大值。

实现细节

• 两个数组都排序后线性扫描即可。指针 pos 单调递增，整个过程每个元素只会被加入一次。
• 注意边界情况：当 B 全部取完仍然无法让 SB ≥ SA 时，仍需记录此时的最坏收益。

复杂度

排序的代价为 $O(n \log n)$，双指针扫描为 $O(n)$，总体时间复杂度 $O(n \log n)$，空间复杂度 $O(n)$。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
double ans,SA,SB,a[N],b[N];
bool cmp(double a,double b){return a>b;}
int main()
{
	int n,pos=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%lf%lf",&a[i],&b[i]);
	sort(a+1,a+1+n,cmp),sort(b+1,b+1+n,cmp);
	for(int i=1;i<=n;i++)
	{
		SA+=a[i];
		ans=max(ans,min(SA-i-pos,SB-i-pos));
		while(pos<n&&SB<SA)SB+=b[++pos],ans=max(ans,min(SA-i-pos,SB-i-pos));
	}
	printf("%.4lf\n",ans);
	return 0;
}