题目链接
题目思路
首先二分k值
然后check的时候有一个很重要的性质
参考这个链接
然后用优先队列维护前k大值,枚举断点,乱搞搞
代码
#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define debug cout<<"I AM HERE"<<endl;
using namespace std;
typedef long long ll;
const int maxn=2e5+5,inf=0x3f3f3f3f,mod=1e9+7;
const double eps=1e-6;
int n;
ll pre[maxn],suf[maxn];
pair<int,int> pa[maxn];
bool cmp(pii a,pii b){
return a.fi+a.se>b.fi+b.se;
}
bool check(int k){
priority_queue<int, vector<int>, greater<int>> q1; //升序
ll temp=0;
for(int i=1;i<=n;i++){
if(i<=k){
q1.push(pa[i].fi);
temp+=pa[i].fi;
}else{
if(q1.top()<pa[i].fi){
temp+=pa[i].fi-q1.top();
q1.pop();
q1.push(pa[i].fi);
}
}
pre[i]=temp;
}
priority_queue<int> q2;
temp=0;
for(int i=n;i>=1;i--){
if(i>=n-k+1){
q2.push(pa[i].se);
temp+=pa[i].se;
}else{
if(q2.top()>pa[i].se){
temp-=q2.top()-pa[i].se;
q2.pop();
q2.push(pa[i].se);
}
}
suf[i]=temp;
}
for(int i=k;i<=n-k;i++){
if(pre[i]-suf[i+1]>=0) return 1;
}
return 0;
}
signed main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&pa[i].fi);
}
for(int i=1;i<=n;i++){
scanf("%d",&pa[i].se);
}
sort(pa+1,pa+1+n,cmp);
int l=1,r=n/2,ans=0;
while(l<=r){
int mid=(l+r)/2;
if(check(mid)){
ans=mid;
l=mid+1;
}else{
r=mid-1;
}
}
printf("%d\n",ans);
return 0;
}