1175C.md (1572B)
1 Source: https://codeforces.com/problemset/problem/1175/C 2 3 C. Electrification 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 At first, there was a legend related to the name of the problem, but now it's just a formal statement. 22 23 You are given $n$ points $a_1, a_2, \dots, a_n$ on the $OX$ axis. Now you are asked to find such an integer point $x$ on $OX$ axis that $f_k(x)$ is minimal possible. 24 25 The function $f_k(x)$ can be described in the following way: 26 27 * form a list of distances $d_1, d_2, \dots, d_n$ where $d_i = |a_i - x|$ (distance between $a_i$ and $x$); 28 * sort list $d$ in non-descending order; 29 * take $d_{k + 1}$ as a result. 30 31 If there are multiple optimal answers you can print any of them. 32 33 Input 34 35 The first line contains single integer $T$ ($ 1 \le T \le 2 \cdot 10^5$) — number of queries. Next $2 \cdot T$ lines contain descriptions of queries. All queries are independent. 36 37 The first line of each query contains two integers $n$, $k$ ($1 \le n \le 2 \cdot 10^5$, $0 \le k \lt n$) — the number of points and constant $k$. 38 39 The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_1 \lt a_2 \lt \dots \lt a_n \le 10^9$) — points in ascending order. 40 41 It's guaranteed that $\sum{n}$ doesn't exceed $2 \cdot 10^5$. 42 43 Output 44 45 Print $T$ integers — corresponding points $x$ which have minimal possible value of $f_k(x)$. If there are multiple answers you can print any of them. 46 47 Example 48 49 Input 50 51 ``` 52 3 53 3 2 54 1 2 5 55 2 1 56 1 1000000000 57 1 0 58 4 59 ``` 60 61 Output 62 63 ``` 64 3 65 500000000 66 4 67 ```