Electrification (Codeforces 1175C)
Tags: Greedy, binary search

At first, there was a legend related to the name of the problem, but now it's just a formal statement.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.The function $$$f_k(x)$$$ can be described in the following way:   form a list of distances $$$d_1, d_2, \dots, d_n$$$ where $$$d_i = |a_i - x|$$$ (distance between $$$a_i$$$ and $$$x$$$);  sort list $$$d$$$ in non-descending order;  take $$$d_{k + 1}$$$ as a result. If there are multiple optimal answers you can print any of them.

Input: 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. The first line of each query contains two integers $$$n$$$, $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$0 \le k < n$$$) — the number of points and constant $$$k$$$.The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_1 < a_2 < \dots < a_n \le 10^9$$$) — points in ascending order.It's guaranteed that $$$\sum{n}$$$ doesn't exceed $$$2 \cdot 10^5$$$.

Output: 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.


Sample Inputs:
3
3 2
1 2 5
2 1
1 1000000000
1 0
4

Sample Outputs:
3
500000000
4

Solution (Python):
from sys import stdin

def solve():
    results = []
    for _ in range(int(stdin.readline())):
        (n, k) = map(int, stdin.readline().split())
        a = [int(x) for x in stdin.readline().split()]
        (i, s) = (0, 0)
        while i + k < n:
            if a[i + k] - a[i] < a[s + k] - a[s]:
                s = i
            i += 1
        results.append((a[s] + a[s + k]) // 2)
    print('\n'.join(map(str, results)))
if __name__ == '__main__':
    solve()

Solution (Python):
def solve(n, k, ary):
    if k == 0:
        return ary[0]
    cur = ary[k] - ary[0]
    tmp = cur
    idx = 0
    for i in range(k + 1, n):
        cur = ary[i] - ary[i - k]
        if cur < tmp:
            tmp = cur
            idx = i - k
    mid = tmp // 2
    return ary[idx] + mid

def stdin():
    cases = int(input())
    outs = []
    for i in range(cases):
        nk = input()
        if nk == '1 0':
            res = input()
        else:
            (n, k) = nk.split(' ', 1)
            ary = list(map(int, input().split()))
            res = solve(int(n), int(k), ary)
        outs.append(res)
    print(*outs)
if __name__ == '__main__':
    stdin()

Solution (Python):
import sys
input = sys.stdin.readline
for _ in range(int(input())):
    (n, k) = map(int, input().split())
    A = list(map(int, input().split()))
    ans = 10 ** 10
    if n == 1:
        print(A[0])
    else:
        for i in range(n - k):
            if ans > A[i + k] - A[i]:
                m = i
                ans = A[i + k] - A[i]
        print((A[m + k] + A[m]) // 2)