题意

题目链接。

有两组物品，每个物品都有一定的价值，你需要选择若干个物品，收益为两组物品中价值和较少的那组物品的价值和减去所选取的所有物品数。使收益最大化。

解析

发现肯定优先选择价值高的物品。

发现如果已经选择了若干个物品，接下来那个物品只有选择当前总价值低的那一组才有可能有更优解。

由上，本题可以用双指针解决。对于两组物品分别用一个指针维护，再依次尝试选择总价值低的那一组，在过程中统计答案。第一个物品可以随意选择，因为不可能出现一组选一组不选的情况，这还不如啥都不选。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,l,r;//l：A组,r:B组
double a[N],b[N],ans,suma,sumb;
inline bool cmp(double i,double j){
    return i>j;
}
int main(){
    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(r=1;r<=n;r++){//双指针
        sumb+=b[r];ans=max(ans,min(suma-(l+r),sumb-(l+r)));
        while(suma<sumb&&l<n){//尝试选择当前总价值低的那组
            suma+=a[++l];
            ans=max(ans,min(suma-(l+r),sumb-(l+r)));
        }
    }
    printf("%.4lf\n",ans);
    return 0;
}