P4653 有两组物品,每个物品都有一定的价值,你需要选择若干个物品,收益为两组物品中价值和较少的那组物品的价值和减去所选取的所有物品数。使收益最大化。
贪心。最大化价值考虑先选大的,尽量维持两堆 \(S\) 平均保持最小值不要相差太大。双指针维护。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define For(i,l,r) for(int i=l;i<=r;i++)
int n;
const int N=1e5+10;
#define db double
db a[N],b[N];
db ans;
db sa,sb;
int main(){cin>>n;For(i,1,n)cin>>a[i]>>b[i];sort(a+1,a+n+1);sort(b+1,b+n+1);reverse(a+1,a+n+1);reverse(b+1,b+n+1);
// For(i,1,n)cout<<a[i]<<" ";
// cout<<"\n";int l=0;For(r,1,n){sb+=b[r];int len=l+r;ans=max(ans,min(sa-len,sb-len));//价值和-长度while(sa<sb&&l<n){l++;sa+=a[l];len=l+r;ans=max(ans,min(sa-len,sb-len));//价值和-长度}}cout<<fixed<<setprecision(4)<<ans;return 0;
}