USACO Sabotage

洛谷 P2115 [USACO14MAR]破坏Sabotage

https://www.luogu.org/problem/P2115

JDOJ 2418: USACO 2014 Mar Gold 2.Sabotage

https://neooj.com/oldoj/problem.php?id=2418

Description

Problem 2: Sabotage [Brian Dean, 2014]

Farmer John's arch-nemesis, Farmer Paul, has decided to sabotage Farmer
John's milking equipment!

FP是FJ的死对头，他想破坏FJ的挤奶系统。

The milking equipment consists of a row of N (3 <= N <= 100,000)
milking machines, where the ith machine produces M_i units of milk (1
< = M_i <= 10,000). Farmer Paul plans to disconnect a contiguous block
of these machines -- from the ith machine up to the jth machine (2 <=
i <= j <= N-1); note that Farmer Paul does not want to disconnect
either the first or the last machine, since this will make his plot
too easy to discover. Farmer Paul's goal is to minimize the average
milk production of the remaining machines. Farmer Paul plans to
remove at least 1 cow, even if it would be better for him to avoid
sabotage entirely.

FJ的挤奶系统包含一行共N(3 <= N <= 100,000)个挤奶器，其中第i号挤奶器可以挤M_i(1<= M_i <= 10,000)升牛奶。
FP打算破坏从第i号到第j号这连续的一段挤奶器(2 <=i <= j <= N-1)，但保罗不打算破坏第1号和第N号挤奶器。
FP想要达到的目的是使得剩下的挤奶器的平均产量尽可能低。FP至少要破坏一个挤奶器。

Fortunately, Farmer John has learned of Farmer Paul's evil plot, and
he is wondering how bad his milk production will suffer if the plot
succeeds. Please help Farmer John figure out the minimum average milk
production of the remaining machines if Farmer Paul does succeed.

求这个最低的平均产量。

Input

* Line 1: The integer N.

* Lines 2..1+N: Line i+1 contains M_i.

Output

* Line 1: The lowest possible average Farmer Paul can achieve, rounded
to 3 digits after the decimal point, and printed with 3 digits
after the decimal point.

Sample Input

5 5 1 7 8 2

Sample Output

2.667

HINT

OUTPUT DETAILS:

The optimal solution is to remove the 7 and 8, leaving 5, 1, and 2, whose
average is 8/3.

我个人觉得这题像是一个数学题。
因为是一段连续的数列，所以自然而然地想到维护一个前缀和数组，并且采用二分答案来优化枚举平均值。

对于每一个平均值，我们怎么判断呢？

设去掉[i,j]区间，去掉的和就是sum[j]-sum[i-1]，剩下的和就是sum[n]-(sum[j]-sum[i-1])，去括号，sum[n]-sum[j]+sum[i-1]

也就是[j,n]的和加上[1,i-1]的和

剩下的个数n-(j-i+1)

所以我们得出了判断条件：

(sum[n]-sum[j]+sum[i-1])/(n-j+i-1)<=x

然后运用浮点型二分来AC：

#include<cstdio>
#include<algorithm>
using namespace std;
int sum[100001]; 
int n;
bool check(double x)
{
    double minv = sum[1]-x*1; 
    for(int i=2;i<n;i++)
    {
        if (sum[n]-x*n-(sum[i]-x*i)+minv<=0) 
            return 1;
        minv=min(minv,sum[i]-x*i);   
    }
    return 0;
}
int main()
{
    scanf("%d",&n);
    for (int i=1; i<=n; i++)
    {
        int a;
        scanf("%d",&a);
        sum[i] = sum[i-1]+a;
    }
    double l = 0, r = 10000;
    while(r-l>1e-5)   
    {
        double mid = (l+r)/2;
        if (check(mid)) 
            r = mid;    
        else 
            l = mid;
    }
    printf("%.3lf",r);
    return 0;
}