EducationalCodeforcesRound66(RatedforDiv.2)C.Electrification

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 a1,a2,…,an on the OX axis. Now you are asked to find such an integer point x on OX axis that fk(x) is minimal possible.

The function fk(x) can be described in the following way:

form a list of distances d1,d2,…,dn where di&＃61;|ai−x| (distance between ai and x);
sort list d in non-descending order;
take dk&＃43;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≤T≤2⋅105) — number of queries. Next 2⋅T lines contain descriptions of queries. All queries are independent.

The first line of each query contains two integers n, k (1≤n≤2⋅105, 0≤k

The second line contains n integers a1,a2,…,an (1≤a1

It’s guaranteed that ∑n doesn’t exceed 2⋅105.

Output
Print T integers — corresponding points x which have minimal possible value of fk(x). If there are multiple answers you can print any of them.

Example
inputCopy
3
3 2
1 2 5
2 1
1 1000000000
1 0
4
outputCopy
3
500000000
4

题目思路&＃xff1a;枚举i从1到i&＃43;m<&＃61;n的每一个下标&＃xff0c;查看每一个的首位相见大小&＃xff0c;找最小的

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define dd double
using namespace std;ll a[200005];
ll inf &＃61; 1e14 &＃43; 10;int main() {ios::sync_with_stdio(0);ll t; cin >> t;while (t--) {ll n, m;cin >> n >> m;for (ll i &＃61; 1; i <&＃61; n; i&＃43;&＃43;) {cin >> a[i];}ll maxx &＃61; inf, ans;for (ll i &＃61; 1; i &＃43; m <&＃61; n; i&＃43;&＃43;) {if (maxx > a[i &＃43; m] - a[i]) {maxx &＃61; a[i &＃43; m] - a[i];ans &＃61; (a[i &＃43; m] &＃43; a[i]) / 2;}}cout << ans << endl;}
}