noiac64 sort (二分答案)

157 阅读 0 评论 104 点赞

我是靠谱客的博主复杂小天鹅，这篇文章主要介绍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 }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
 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 }