[二分][贪心]JZOJ P3996 Sabotage

Description

FJ 的死对头，FP，现在决定了去破坏FJ 的挤奶设备！
这个挤奶设备由一行N（3 <= N<= 100, 000）个挤奶机器，其中第i 个机器生产Mi 单位的牛奶（1<= Mi <= 10, 000）。FP 计划将机器连续的一块断开——从第i 个机器到第j 个机器（2<= i<= j<= N-1）；注意第一个和最后一个机器FJ 并不想要断开，因为这会让这次事件太容易被发现。FP 的目标是让剩下的机器的牛奶平均产量最小。FP 打算移去至少一台机器，即使对他来说不进行破坏更好。
幸运的是，FJ 已获悉FP 的邪恶计划，并且他想知道如果计划成功他的挤奶设备会被破坏成什么样。请帮助FJ 找到，如果FP 成功，最小的剩下挤奶机器的平均生产量。

Input

第一行：整数N。
第2 至N + 1 行：第i + 1 行包含Mi。

Output

输出单独一行一个整数——FP 能获得的最小的可能的平均数，四舍五入到小数点后3 位数字，小数点后三位数字都要输出。

Sample Input

Sample Output

2.667
样例解释：
最佳方案是移除7 和8，留下5; 1 以及2，使得平均值为8/3。

Data Constraint

对于14% 的数据，有N<=10。
对于49% 的数据，有N <=1000。

题解

我们可以考虑一下二分平均数
那么我们怎么判断当前二分出来的值可不可行呢
首先，我们可以先将每一个数减去一个平均数，存在数组f
那么显然，如果当前f数组中数的和为0，那么这组数的平均数就是这次二分出来的值mid
所以，我们对于当前二分出来的值返回true的条件：数组f中减去连续一段最大的数之后的和小于等于mid
问题就转换为求一段最大的数
很容易想到，[l,r]一段的和=[1,r]-[1,l]
所以，贪心的思想就是[1,l]尽量小，[1,r]尽量大
注意要取小数点后三位

代码

 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 int n;
 5 double l,r,mid,x1,x2,f[100010],a[100010];
 6 bool pd(double x)
 7 {
 8     for (int i=1;i<=n;i++) f[i]=f[i-1]+a[i]-x;
 9     x1=a[1]; x2=a[2]-x;
10     for (int i=2;i<=n-1;i++)
11     {
12         if (x1>f[i-1]) x1=f[i-1];
13         if (x2<f[i]-x1) x2=f[i]-x1;
14     }
15     if (f[n]-x2<=0) return true; else return false;
16 }
17 int main()
18 {
19     scanf("%d",&n);
20     for (int i=1;i<=n;i++) 
21     {
22         scanf("%lf",&a[i]);
23         if (a[i]>r) r=a[i];
24     }
25     while (l<=r)
26     {
27         mid=(l+r)/2;
28         if (r-l<0.0001) break;
29         if (pd(mid)) r=mid; else l=mid;
30     }
31     printf("%.3lf",l);
32 }