E
l
e
c
t
r
i
f
i
c
a
t
i
o
n
Electrification
Electrification
题目描述见链接 .
正
解
部
分
\color{red}{正解部分}
正解部分
将
{
a
i
}
\{a_i\}
{ai} 放到数轴中, 题意转化 为: 在数轴上选择一个点
x
x
x , 使得与
x
x
x 距离第
K
K
K 大的点 到
x
x
x 的距离
d
d
d 最小 .
d
d
d 显然是具有 单调性 的, 考虑 二分答案, 二分出
d
d
d, 再考虑怎么检查
d
d
d 是否合法,
当
[
x
−
d
,
x
+
d
]
[x-d, x+d]
[x−d,x+d] 中的 点数 不超过
K
K
K 个时, 说明
x
x
x 合法, 但是直接枚举
x
x
x 去检查
d
d
d 是否合法显然会
T
L
E
TLE
TLE, 考虑更快的方法,
枚举 左端点
a
l
a_l
al, 设
y
=
l
+
K
−
1
y = l+K-1
y=l+K−1, 右端点
a
r
a_r
ar, 若
a
r
−
a
l
≤
2
d
→
a
r
−
a
l
2
≤
d
a_r - a_l \le 2d \rightarrow \frac{a_r-a_l}{2} \le d
ar−al≤2d→2ar−al≤d , 说明
x
=
⌊
a
l
+
a
r
2
⌋
x = \lfloor \frac{a_l+a_r}{2} \rfloor
x=⌊2al+ar⌋ 时, 距离
x
x
x 第
K
K
K 近的点距离不超过
d
d
d, 符合题目要求 .
于是就可以
O
(
n
)
O(n)
O(n)
c
h
e
c
k
check
check 了 .
实
现
部
分
\color{red}{实现部分}
实现部分
#include<bits/stdc++.h>
#define reg register
const int maxn
= 2e5 + 10;
int read(){
char c
;
int s
= 0, flag
= 1;
while((c
=getchar()) && !isdigit(c
))
if(c
== '-'){ flag
= -1, c
= getchar(); break ; }
while(isdigit(c
)) s
= s
*10 + c
-'0', c
= getchar();
return s
* flag
;
}
int N
;
int K
;
int Ans
;
int A
[maxn
];
bool check(int x
){
for(reg
int i
= 1; i
+K
-1 <= N
; i
++){
int j
= i
+ K
- 1;
if(A
[j
]-A
[i
] <= (x
<< 1)){ Ans
= A
[i
]+A
[j
] >> 1; return true; }
}
return false;
}
void Work(){
N
= read(), K
= read() + 1;
for(reg
int i
= 1; i
<= N
; i
++) A
[i
] = read();
int l
= 0, r
= A
[N
] - A
[1];
while(l
<= r
){
int mid
= l
+r
>> 1;
if(check(mid
)) r
= mid
- 1;
else l
= mid
+ 1;
}
printf("%d\n", Ans
);
}
int main(){
int T
= read();
while(T
--) Work();
return 0;
}
