本文共 1998 字，大约阅读时间需要 6 分钟。

链接：

时间限制：C/C++ 1秒，其他语言2秒

题目描述

巨佬 lzy\text{lzy}lzy 闲来无事，给了蒟蒻 brz\text{brz}brz 一个长度为 n 的序列 a，并且允许蒟蒻操作这个序列，巨佬 lzy\text{lzy}lzy 定义，一次操作要选定一个 i∈(1,n)i\in(1,n)i∈(1,n)，然后将序列中第 i 个数变成与它相邻的两个数的平均数，即 ai=ai−1+ai+12a_i=\dfrac {a_{i-1}+a_{i+1}} 2ai​=2ai−1​+ai+1​​。

输入描述:

第一行一个整数n，表示序列长度。

第二行n个整数，表示这个序列。

1≤n≤106,1≤ai≤1091\leq n\leq 10^6,1\leq a_i\leq 10^91≤n≤106,1≤ai​≤109

输出描述:

输出一个实数，表示能得到的序列最小总和，保留到小数点后十位。

示例1

输入

31 2 2

输出

4.5000000000

说明

操作一次序列的第二个数，使其变成1+2​=1.5，序列总和就是1+1.5+2=4.5，可以证明序列总和无法变得更小。

思路：

可以发现当一个区间变成等差数列时就不能再变小了，问题进一步转化为从原序列中选择一些区间将其变为等差数列。

并不是任意区间变成等差数列时的和最小，只有除首尾以外的数都大于等差数列上对应的数时，原区间的和才会是最小值。

把序列中的数  抽象为坐标系中的点 ，问题转化为了求下凸壳，（由于原序列已经按x坐标排序，所以本题不需要提前极角排序

#include
   
    using namespace std;typedef long long ll;const double eps = 1e-11;const int N = 1e6 + 10;int sgn(double x) {    if(fabs(x) < eps) return 0;    if(x < 0) return -1;    else return 1;}struct Point{	double x, y;	Point(){}	//定义运算	Point(double _x, double _y) {        x = _x;        y = _y;    }	bool operator == (Point b) const {        return sgn(x - b.x) == 0 && sgn(y - b.y) == 0;	}	bool operator < (Point b) const {        return sgn(x - b.x) == 0 ? sgn(y - b.y) < 0 : x < b.x;	}	Point operator - (const Point &b) const {        return Point(x - b.x, y - b.y);	}    double operator ^ (const Point &b) const {        return x * b.y - y * b.x;	}} p[N], st[N];int main() {    int n;    scanf("%d", &n);    for(int i = 1; i <= n; ++i) {        scanf("%lf", &p[i].y);        p[i].x = 1.0 * i;    }    int top = 0;    for(int i = 1; i <= n; ++i) {        while(top > 1 && ((p[i] - st[top - 1]) ^ (st[top] - st[top - 1])) > 0.0) --top;        st[++top] = p[i];    }    double ans = 0.0;    for(int i = 2; i <= top; ++i)        ans += 1.0 * (st[i].y + st[i - 1].y) * (st[i].x - st[i - 1].x + 1) / 2.0 - st[i].y;    ans += st[top].y;    printf("%.10f\n", ans);    return 0;}