E.Arithmetics Competition
原题链接
题意简述
在算术比赛中，参赛者需要用手中的纸牌算出尽可能高的总和。在 "fst_ezik "队中，瓦迪姆有 \(n\) 张数字为 \(a_i\) 的牌，科斯佳有 \(m\) 张数字为 \(b_i\) 的牌。在每一轮 \(q\) 比赛中，他们都想获胜，但这次的比赛规则与往常略有不同。
在每一轮比赛中，参赛者都会得到三个数字 \(x_i\) 、\(y_i\) 和 \(z_i\) 。" fst_ezik "队必须从他们所有的牌中准确地选出 \(z_i\) 张牌，但是瓦迪姆从他的牌组中选出的牌不能超过 \(x_i\) 张，科斯佳从他的牌组中选出的牌不能超过 \(y_i\) 张。请帮助他们找出\(q\) 轮的最高和。
解题思路
两个序列中选择k个最大值，但是序列a选择数量不超过 x，序列b中选择数量不超过y，
solve1.考虑把 a 从小到大排序，把 b 从大到小排序，构造一个凸函数，但是由于区间是非严格的凸性，三分法时取前缀和区间选取范围卡到 r-l>=6
solve2:把 a 从小到大排序，把 b 从小到大排序，然后合并 a 与 b 中元素到 c 从小到大排序，观察 c 中前 k位 元素 选取的a数量是否满足 a<=x ,不满足则输出 a 中前 x 大之和 与 b 中 前 k-x 大 之和相加 ， 选取的b数量是否满足 b<=y ,不满足则输出 b 中前 y 大之和 与 a 中 前 k-y 大 之和相加 ，如果都满足，直接输出合并区间中前 k 大的数即可.
AC code(三分)
//Stop learning useless algorithms, go and solve some problems, learn how to use binary search.
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
void solve(){int n,m,q;cin>>n>>m>>q;vector<ll>a(n+m+1);for(int i=1;i<=n+m;i++) cin>>a[i];sort(a.begin()+1,a.begin()+1+n);sort(a.begin()+1+n,a.end(),greater<ll>());vector<ll>pre(n+m+1);for(int i=1;i<=n+m;i++) pre[i]=pre[i-1]+a[i];auto f=[&](int mid,int k) ->ll {if(mid<k) return -INT_MAX;return pre[mid]-pre[mid-k];};while(q--){int x,y,z;cin>>x>>y>>z;int l=n-x+z,r=n+y;while(r-l>=6){int mid1=l+(r-l)/3;int mid2=r-(r-l)/3;if(f(mid1,z)<f(mid2,z)) l=mid1;else r=mid2;}ll ans=0;for(int i=l;i<=r;i++) ans=max(ans,f(i,z));cout<<ans<<endl;}}
int main(){cin.tie(0)->ios::sync_with_stdio(false);int T=1;cin>>T;while(T--) solve();return 0;
}
AC code
//Stop learning useless algorithms, go and solve some problems, learn how to use binary search.
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
void solve(){int n,m,q;cin>>n>>m>>q;vector<ll>a(n+1),b(m+1);vector<pair<int,int>>c(n+m+1);vector<ll>pre(n+m+1);for(int i=1;i<=n;i++) cin>>a[i],c[i].first=a[i],c[i].second=1;for(int i=1;i<=m;i++) cin>>b[i],c[i+n].first=b[i];sort(a.begin()+1,a.end(),greater<ll>());sort(b.begin()+1,b.end(),greater<ll>());sort(c.begin()+1,c.end(),greater< pair<ll,int> >());for(int i=1;i<=n;i++) a[i]+=a[i-1];for(int i=1;i<=m;i++) b[i]+=b[i-1];for(int i=1;i<=n+m;i++) c[i].second+=c[i-1].second;while(q--){int x,y,z;cin>>x>>y>>z;int numa=c[z].second;int numb=z-numa; if(numa>x) cout<<a[x]+b[z-x]<<endl;else if(numb>y) cout<<a[z-y]+b[y]<<endl;else cout<<a[numa]+b[numb]<<endl;}
}
int main(){cin.tie(0)->ios::sync_with_stdio(false);int T=1;cin>>T;while(T--) solve();return 0;
}