【二分】P7795 [COCI2014-2015#7] PROSJEK 题解

P7795

典。

显然 \(\mathcal{O}(n ^ 2)\) 的时间复杂度无法通过。

使子段平均值最大，考虑二分。

可以二分平均值 \(mid\)，然后判断是否有满足条件的子段.

时间复杂度：\(\mathcal{O}(\dfrac{n\log\max\{a_i\}}{\text{eps}})\)，其中 \(\text{eps}\) 为设置的精度，\(\max\{a _ i\} \leq 10^6\)。

代码：

const int N = 3e5 + 5;
const double eps = 1e-6;
int n, k;
int a[N];
double b[N];

bool check(double mid) {
	for (int i = 1; i <= n; i++) {
		b[i] = b[i - 1] + a[i] - mid;
	}
	double res = -1, mnv = 1e9;
	for (int i = k; i <= n; i++) {
		mnv = std::min(mnv, b[i - k]);
		res = std::max(res, b[i] - mnv);
	}
	return res >= 0;
}

int main() {
	scanf("%d %d", &n, &k);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	double l = 1, r = 1e6;
	while (l + eps < r) {
		double mid = (l + r) / 2;
		if (check(mid))
			l = mid;
		else
			r = mid;
	}
	printf("%.6lf\n", l);
	return 0;
}