题解
着重点:分类讨论+二分中位数
首先,由于要求中位数,我们先将数组进行排序;接着我们取遍所有的ai及其对应中位数。
此时,分歧产生,我们有k次增值的机会,是加到ai(不会改变中位数)上 还是 增值后改变中位数(此时中位数可能改变)?
显然,我们要分类讨论
情况一:我们加到选取的ai上,显然只要bi=1,直接将所有k加给ai即可。
情况二:改变中位数,此时显然我们选择的ai是最大值(贪心);直接求最大中位数不好求,我们将通过二分寻找最大中位数(具体实现看code)。
code
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e5+5; int n,k; struct node{ ll a; int b,id; bool operator<(const node &m){ if (a!=m.a) return a<m.a; if (b!=m.b) return b<m.b; return id<m.id; } }; node p[N]; bool check(int m){ int cnt=0,sum=k; for (int i=n-1;i>=1;i--){ if (p[i].a>=m) cnt++; else{ if (p[i].b){ if (sum>=m-p[i].a){ sum-=m-p[i].a; cnt++; } else break; } } } if (cnt>=n-n/2) return true; return false; } void solve(int t){ cin>>n>>k; ll MAX=0; for (int i=1;i<=n;i++) cin>>p[i].a; for (int i=1;i<=n;i++){ cin>>p[i].b; p[i].id=i; } sort(p+1,p+1+n); int cnt=n/2; ll ans=0; if (p[n].b) ans=max(ans,p[n].a+p[cnt].a+ll(k)); else{ ll l=p[cnt].a,r=p[cnt].a+k+1; while (l+1<r){ ll mid=(l+r)/2ll; if (check(mid)) l=mid; else r=mid; } ans=max(ans,p[n].a+l); } for (int i=1;i<=n;i++){ if (p[i].b){ if (i<=cnt) ans=max(ans,p[i].a+k+p[cnt+1].a); else ans=max(ans,p[i].a+k+p[cnt].a); } } cout<<ans<<endl; } int main(){ //freopen("input.txt","r",stdin); int t; cin>>t; for (int i=1;i<=t;i++){ solve(i); } return 0; }
标签:Operations,cnt,Perform,ll,中位数,int,ai,Score,ans From: https://www.cnblogs.com/purple123/p/18355936