【Code Forces 320E】【三分+前缀和】Weakness and Poorness 最大的区间和的绝对值尽可能小

本文主要是介绍【Code Forces 320E】【三分+前缀和】Weakness and Poorness 最大的区间和的绝对值尽可能小，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【传送门】
http://codeforces.com/contest/579/problem/E

【题意】
给你一个整数数列a1~an
找到一个实数x，使得a1-x,a2-x,…,an-x的weakness尽可能小
一个数列的weakness，是这个数列所有区间poorness的最大值
一个区间的poorness，是这个区间内所有元素和的绝对值

也就是我们想找到一个实数x，使得
a1-x,a2-x,…,an-x内的所有区间段中(C(n,2)+C(n,1)个)，
最大的元素的和绝对值尽可能小。

【类型】
三分+前缀和

【分析】
使得最大值尽可能小，感觉就是二分（三分）。

第一个问题——
x的改变，答案是否会产生单调性的变化？
首先，所有数都是在-10000~10000之间的，
如果x比-10000还小，x越小肯定答案越糟糕
同理，如果x比10000还大，那么x越大，答案也会越糟糕。
那，如果x在[min(a[i]),max(a[i])]区间范围内呢？

和诗诗讨论了40分钟，终于讨论出来了，好开心O(∩_∩)O~

我们定义横坐标为x，纵坐标为区间内所有数-x之后和的绝对值
于是，对于一个长度为n区间而言，设初始和为sum，在这个坐标系上，函数为abs(sum-nx)
就是一条斜率是±n的折线，对于这个折线，我们是可以三分求最低值的。

而现在有多个区间，我们可以把它们都画在这个坐标图上，
这里其实有一个结论——多个开口方向相同的二次曲线，我们取max值，得到的函数曲线（也就是这道题关于x的答案曲线），虽然是多段，但依然具有三分性
（对于这道题的模型和坐标系，也必定满足先递减后递增）

于是可以三分！

第二个问题——
在x为某个值的情况下，我们怎么求元素的和绝对值最大的那个的区间段的元素和的绝对值？

对于区间最值，
要不我们可以通过数据结构维护，要不就通过前缀和。
数据结构？因为有绝对值，所以感觉不会写。
前缀和？但是这道题有前缀和的加减法性质么？

我们发现——
如果先对每个点求完绝对值，那就没有加减法性质了，因为我们不知道是相加关系还是相消关系。
然而只是数值而言的话，是满足前缀和性质。于是我们可以维护一个前缀和，不涉及到绝对值。
连续区间段的和就是两个前缀和相减。

所以说我们只要记录在这个前缀和之前，最大的前缀和还有最小的前缀和。
然后就能对应出最大的差值，得到最大的区间和的绝对值。
这样是可以在O(n)的时间复杂度更新出的。

【时间复杂度&&优化】
O(nlog(20000))
这题还有考虑上凸包或下凸包的O(n)解法，然而我并不会QwQ

【trick】
为了控制精度误差，不用eps，而用循环次数永远都是不错的选择。

【数据】
Input
3 1 2
1 1 1
Output
3

Input
4 2 3
1 2 4 8
Output
79

【代码】

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<ctype.h>
#include<math.h>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<functional>
#include<string>
#include<algorithm>
#include<time.h>
#include<bitset>
void fre(){freopen("c://test//input.in","r",stdin);freopen("c://test//output.out","w",stdout);}
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x,y) memcpy(x,y,sizeof(x))
#define MP(x,y) make_pair(x,y)
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T> inline void gmax(T &a,T b){if(b>a)a=b;}
template <class T> inline void gmin(T &a,T b){if(b<a)a=b;}
using namespace std;
const int N=2e5+10,M=0,Z=1e9+7,maxint=2147483647,ms31=522133279,ms63=1061109567,ms127=2139062143;const double eps=1e-8,PI=acos(-1.0);//.0
map<int,int>mop;
struct A{};
int n;
double a[N],b[N];
double cnt(double x)
{for(int i=1;i<=n;i++)b[i]=a[i]-x;double minv=0;//积累前缀和的最小值double maxv=0;//积累前缀和的最大值double sum=0;//积累前缀和double tmp=0;//利用前三项，积累得到最大区间差值for(int i=1;i<=n;i++){sum+=b[i];gmax(tmp,sum-minv);gmax(tmp,maxv-sum);gmax(maxv,sum);gmin(minv,sum);}return tmp;
}
int main()
{while(~scanf("%d",&n)){for(int i=1;i<=n;i++)scanf("%lf",&a[i]);double l=-10000;double r=10000;double ans=1e18;for(int tim=1;tim<=100;tim++){double lm=(l+l+r)/3;double tmpl=cnt(lm);double rm=(l+r+r)/3;double tmpr=cnt(rm);if(tmpl<=tmpr)r=rm;else l=lm;}printf("%.12f\n",cnt(l));}return 0;
}