noiac64 sort (二分答案)

首先如果L=1,那就可以直接用一个优先队列来做

但它并不是1 所以要换个做法

假设我们已经知道第L的数是x,第R的数是y

那其实就只需要找到[x+1,y+1]这一段,然后再加上一定数量的x和y就是答案

于是可以枚举A[i],二分B[j]找到

然后考虑怎么找第L的数是多少

其实也是二分出一个数,然后比较L和小于它的个数

这个小于它的个数怎么算呢,还是二分......

复杂度$O(nlog^2n)$

 #include<bits/stdc++.h>
#define pa pair<int,int>
#define CLR(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=1e5+; inline ll rd(){
ll x=;char c=getchar();int neg=;
while(c<''||c>''){if(c=='-') neg=-;c=getchar();}
while(c>=''&&c<='') x=x*+c-'',c=getchar();
return x*neg;
} ll N,L,R,a[maxn],b[maxn],ans[maxn]; inline ll count(ll k){
ll re=;
for(int i=;i<=N;i++){
int l=,r=N,n=;
while(l<=r){
int m=l+r>>;
if(a[i]+b[m]<k) l=m+,n=m;
else r=m-;
}re+=n;
}return re;
} int main(){
ll i,j,k;
N=rd(),L=rd(),R=rd();
for(i=;i<=N;i++)
a[i]=rd();
for(i=;i<=N;i++)
b[i]=rd();
sort(a+,a+N+);sort(b+,b+N+);
ll l=a[]+b[],r=a[N]+b[N],nl,nr;
while(l<=r){
int m=l+r>>;
if(count(m)<L) l=m+,nl=m;
else r=m-;
}
l=a[]+b[],r=a[N]+b[N];
while(l<=r){
int m=l+r>>;
if(count(m)<R) l=m+,nr=m;
else r=m-;
}
k=;
for(i=;i<=N;i++){
int l=,r=N,x=N+,y=-;
while(l<=r){
int m=l+r>>;
if(a[i]+b[m]>nl) x=m,r=m-;
else l=m+;
}
l=,r=N;
while(l<=r){
int m=l+r>>;
if(a[i]+b[m]<nr) y=m,l=m+;
else r=m-;
}
for(j=x;j<=y;j++)
ans[++k]=a[i]+b[j];
}
sort(ans+,ans+k+);
for(i=L;i<=min(R,count(nl+));i++)
printf("%lld ",nl);
j=i-;
for(;i<=k+j;i++)
printf("%lld ",ans[i-j]);
for(;i<=R;i++)
printf("%lld ",nr);
return ;
}
上一篇:转:VMware中CentOS配置静态IP进行网络访问(NAT方式和桥接模式)


下一篇:VMware虚拟机下Centos8 设置静态IP地址