洛谷P2115 Sabotage G 题解

题目

[USACO14MAR]Sabotage G

题解

本蒟蒻又来了，这道题可以用二分答案来解决。我们可以设答案最小平均产奶量为 \(x \ (x \in[1,10000])\) 。然后二分搜索 \(x\) 的最小值。

\[\frac{sum-sum[l,r]}{n-(r-l+1)}\leq x
\]

\[nx-(r-l+1)x\geq sum-sum[l,r]
\]

\[sum-nx \leq \sum\limits_{i=l}^r{(a[i]-x)}
\]

对于如何求 \(\sum\limits_{i=l}^r{(a[i]-x)}\) 的最大值，这个很简单，套用最大子段和的解法即可。

最后根据 \(sum-nx \leq \sum\limits_{i=l}^r{(a[i]-x)}\) 的判断结果来调整二分搜索的区间即可，直至区间长度 \(< 10^{-5}\) 。

贴一下代码

#include<iostream>

using namespace std;

const double e = 1e-5;

int n, a[100001];

double sum = 0;

bool check(double x)

{

	double snx = sum - n * x;

	double s = 0;

	for (int i = 2; i < n; i++)

	{

		s += a[i] - x;

		if (s >= snx)

			return 1;

		if (s < 0)

			s = 0;

	}

	return 0;

}

int main()

{

	scanf("%d", &n);

	for (int i = 1; i <= n; i++)

	{

		scanf("%d", &a[i]);

		sum += a[i];

	}

	double l = 1, r = 10000;

	while (r-l>=e)

	{

		double mid = (l + r) / 2;

		if (check(mid))

			r = mid;

		else

			l = mid+e;

	}

	printf("%.3lf",l);

	return 0;

}

巴特西

洛谷P2115 Sabotage G 题解

题目

题解

贴一下代码

最新文章

热门文章