【题解】CF1175C：Electrification

原题传送门
二分最优值，然后$O(n)$验证
对于每个$i$，就是看$[i,i+k]$这段区间能不能达到这个最优值
就是$[\frac{a_{i+k}-a_i+1}{2}]<=mid$，可行的话，答案就是$[\frac{a_{i+k}+a_i+1}{2}]$

Code：

#include <bits/stdc++.h>
#define maxn 200010
using namespace std;
int a[maxn], n, k;

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

int main(){
	int T = read();
	while (T--){
		n = read(), k = read();
		for (int i = 1; i <= n; ++i) a[i] = read();
		int l = 0, r = a[n], ans;
		while (l <= r){
			int mid = (l + r) >> 1, flag = 0;
			for (int i = 1; i + k <= n; ++i)
				if ((a[i + k] - a[i] + 1) / 2 <= mid){
					flag = 1, ans = (a[i + k] + a[i]) >> 1;
					break;
				}
			if (flag) r = mid - 1; else l = mid + 1;
		}
		printf("%d\n", ans);
	}
	return 0;
}