﻿ 洛谷P2115 [USACO14MAR]破坏Sabotage - 鸿网互联

# 洛谷P2115 [USACO14MAR]破坏Sabotage

## 题目描述

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

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.

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.

```5
5
1
7
8
2```

`2.667`

## 说明

【样例说明】

【数据规模和约定】

【时空限制】

0.2s/128M

sum[n]-sum[j]+sum[i-1]<=xn-xj-x(i-1)；

(sum[n]-xn)-(sum[j]-xj)+(sum[i-1]-x(i-1))<=0； */

``` 1 #include<iostream>
2 #include<cstdio>
3 #include<algorithm>
4 using namespace std;
5 const int MAXN=100001;
7 {
8     char c=getchar();int x=0,f=1;
9     while(c<'0'||c>'9')    {if(c=='-')f=-1;c=getchar();}
10     while(c>='0'&&c<='9')    x=x*10+c-48,c=getchar();return x*f;
11 }
12 int n;
13 int sum[MAXN];
14 bool check(double val)
15 {
16     double now=123456789.00;
17     double nowmin=sum[1]-val;
18     double sumn=sum[n]-val*n;
19     for(int i=2;i<=n-1;i++)
20     {
21         if(sumn-sum[i]+val*i+nowmin<=0)    return 1;
22         if(sum[i-1]-val*(i-1)<nowmin)    nowmin=sum[i-1]-val*(i-1);
23     }
24     return 0;
25 }
26 int main()
27 {
30     double l=1,r=5000000,ans=1;
31     while(r-l>1e-5)
32     {
33         double mid=(r+l)/2.0;
34         if(check(mid))    r=mid;
35         else l=mid;
36     }
37     printf("%.3lf",r);
38     return 0;
39 }```

<