NC212175. brz的序列
描述
巨佬 闲来无事，给了蒟蒻
一个长度为 n 的序列 a，并且允许蒟蒻操作这个序列，巨佬
定义，一次操作要选定一个
，然后将序列中第 i 个数变成与它相邻的两个数的平均数，即
。
蒟蒻 想要将序列的总和变得最小，但是又不太会操作，也不敢在巨佬的面前吱声，于是只好偷偷向你询问：在可以进行无限次任意位置的操作的情况下，能得到的序列最小总和是多少？
输入描述
第一行一个整数n，表示序列长度。
第二行n个整数，表示这个序列。
输出描述
输出一个实数，表示能得到的序列最小总和，保留到小数点后十位。
示例1
输入:
3 1 2 2
输出:
4.5000000000
说明:
操作一次序列的第二个数，使其变成C++(clang++11) 解法, 执行用时: 180ms, 内存消耗: 4312K, 提交时间: 2020-11-06 20:15:57
#include<bits/stdc++.h>
using namespace std;
int n,a[1111111],p[1111111],t;long long ans;
double f(int x,int y){
return (double)(a[x]-a[y])/(x-y);
}
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++)scanf("%d",&a[i]);
for(int i=1;i<n;i++){
while(t&&f(i,p[t])<=f(p[t],p[t-1]))t--;
p[++t]=i;
}ans=a[0]*2;
for(int i=0;i<t;i++){
ans-=a[p[i]]*2;
ans+=1ll*(a[p[i]]+a[p[i+1]])*(p[i+1]-p[i]+1);
}
printf("%lld.%lld000000000",ans/2,ans%2*5);
return 0;
}