noiac64 sort (二分答案)

81 阅读 0 评论 54 点赞

我是靠谱客的博主复杂小天鹅，最近开发中收集的这篇文章主要介绍noiac64 sort (二分答案)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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

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

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

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

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

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

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

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

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

 1 #include<bits/stdc++.h>
 2 #define pa pair<int,int>
 3 #define CLR(a,x) memset(a,x,sizeof(a))
 4 using namespace std;
 5 typedef long long ll;
 6 const int maxn=1e5+10;
 7
 8 inline ll rd(){
 9
ll x=0;char c=getchar();int neg=1;
10
while(c<'0'||c>'9'){if(c=='-') neg=-1;c=getchar();}
11
while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
12
return x*neg;
13 }
14
15 ll N,L,R,a[maxn],b[maxn],ans[maxn];
16
17 inline ll count(ll k){
18
ll re=0;
19
for(int i=1;i<=N;i++){
20
int l=0,r=N,n=0;
21
while(l<=r){
22
int m=l+r>>1;
23
if(a[i]+b[m]<k) l=m+1,n=m;
24
else r=m-1;
25
}re+=n;
26
}return re;
27 }
28
29 int main(){
30 
ll i,j,k;
31
N=rd(),L=rd(),R=rd();
32
for(i=1;i<=N;i++)
33
a[i]=rd();
34
for(i=1;i<=N;i++)
35
b[i]=rd();
36
sort(a+1,a+N+1);sort(b+1,b+N+1);
37
ll l=a[1]+b[1],r=a[N]+b[N],nl,nr;
38
while(l<=r){
39
int m=l+r>>1;
40
if(count(m)<L) l=m+1,nl=m;
41
else r=m-1;
42 
}
43
l=a[1]+b[1],r=a[N]+b[N];
44
while(l<=r){
45
int m=l+r>>1;
46
if(count(m)<R) l=m+1,nr=m;
47
else r=m-1;
48 
}
49
k=0;
50
for(i=1;i<=N;i++){
51
int l=1,r=N,x=N+1,y=-1;
52
while(l<=r){
53
int m=l+r>>1;
54
if(a[i]+b[m]>nl) x=m,r=m-1;
55
else l=m+1;
56 
}
57
l=1,r=N;
58
while(l<=r){
59
int m=l+r>>1;
60
if(a[i]+b[m]<nr) y=m,l=m+1;
61
else r=m-1;
62 
}
63
for(j=x;j<=y;j++)
64
ans[++k]=a[i]+b[j];
65 
}
66
sort(ans+1,ans+k+1);
67
for(i=L;i<=min(R,count(nl+1));i++)
68
printf("%lld ",nl);
69
j=i-1;
70
for(;i<=k+j;i++)
71
printf("%lld ",ans[i-j]);
72
for(;i<=R;i++)
73
printf("%lld ",nr);
74
return 0;
75 }