codeforces round#320 div 1(C構想3点)

このテーマの意味は1つの数列を与えて、本当に負があって、1つの値xを探させます
数列a[1]-x,a[2]-x,....a[n]−xの連続区間と絶対値の最大値は最小であった.
まずxはa 1->anの最大値max_を選択し、最大負の値はsum 1->n、最大正数は0であり、最小値の逆を選択します.
したがって、負の絶対値の最大値の線と負の絶対値の最大値の線はxでmin_->をとるmax_ 範囲内で交差すると、答えの線はV型で、3点でいいです.
次は他の人のコードで、区間の連続最大と使用の非常に精巧さを求めるため、まだ初写の3点があって、勉強して勉強して、

//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <list>
#include <cstdlib>
#include <queue>
#include <stack>
#include <cmath>
#include <bitset>
#include <cassert>
#define ALL(a) a.begin(), a.end()
#define clr(a, x) memset(a, x, sizeof a)
#define X first
#define Y second
#define pb push_back
#define lowbit(x) (x&(-x))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define rep1(i,x,y) for(int i=x;i<=y;i++)
#define rep(i,n) for(int i=0;i<(int)n;i++)
using namespace std;
const double eps = 1e-10;
typedef long long LL;
typedef long long ll;
typedef pair<int, int> pii;
const int oo =0x3f3f3f3f;

const int N = 200005;

int n;

int a[N];

double cal(double x) {
	double mins = 0, maxs = 0, cur = 0, ret = 0;
	for (int i = 0; i < n; ++i) {
		cur += a[i] - x;
		maxs = max(maxs, cur);
		mins = min(mins, cur);
		ret = max(ret, max(maxs - cur, cur - mins));
	}
	return ret;
}

int main() {
	scanf("%d", &n);
	int min_  = 1e9, max_ = - 1e9;
	for (int i = 0; i < n; ++i)  
        scanf("%d", a + i);
	double l = -1e5 - 10, r = 1e5 + 10;
	for (int i = 0; i < 100; ++i) {
		double m1 = (l + l + r) / 3, m2 = (l + r + r) / 3;
		if (cal(m1) < cal(m2)) {
			r = m2;
		} else {
			l = m1;
		}
	}
	printf("%.12f
", cal((l + r) / 2));
	return 0;
}