brz的序列题解

简化题意：多次操作使一个数变成旁边两个数的平均值，求序列中数字和最小是多少。
可以发现当一段区间变成等差数列后就不能再进行修改了。
问题变为选定若干等差数列的首项末项，使数列和最小。
又注意到一段区间能变成等差数列当且仅当这段区间除了首项末项以外的数都比变成等差数列后对应位置上的数大。
于是可以转化问题，有 个点，坐标分别为 。
把一个区间覆盖成等差数列相当于在首尾的点之间连线。
发现要求的实际上就是这些点的下凸壳。
代码如下：

#include <algorithm>
#include <cstdio>

using namespace std ;

typedef long long LL ;
const int N=1e6+10 ;

struct Point
{
    LL x , y ;
    Point ( LL X=0 , LL Y=0 ):x(X),y(Y) {}
    Point operator - ( const Point &p ) const { return (Point){x-p.x,y-p.y}; }
    double operator * ( const Point &p ) const { return x*p.y-y*p.x; }
};
Point p[N] ;
Point stk[N] ;
int top ;

#define calc(a,b,c) ((b-a)*(c-a))

int n ;

int main ()
{
    int i ;
    scanf("%d",&n);
    for ( i=1 ; i<=n ; i++ )
        scanf("%lld",&p[i].y),
        p[i].x=i;
    for ( i=1 ; i<=n ; i++ )
    {
        while ( top>1 && calc(stk[top-1],stk[top],p[i])<=0 ) --top;
        stk[++top]=p[i];
    }
    double res=0 ;
    for ( i=2 ; i<=top ; i++ )
        res+=(double)(stk[i].y+stk[i-1].y)*(double)(stk[i].x-stk[i-1].x+1)/2.0-(double)(stk[i].y);
    res+=(double)stk[top].y;
    printf("%.10lf\n",res);
    return 0 ;
}