『STA - R1』Crossnews之单调栈

『STA - R1』Crossnews

题目背景

Informational problems make us better.

题目描述

定义两个序列 ， 的联合权值为

现给定一个序列 ，求满足 最小的单调不减序列 ，只需输出 的值即可。

注意， 中的元素不一定要为整数。

输入格式

第一行一个正整数 。

第二行 个整数表示。

输出格式

一行一个答案。

样例 #1

样例输入 #1

5

1 2 3 4 5

样例输出 #1

-13.7500000

样例 #2

样例输入 #2

10

1000 1 2 8 9 5 4 1000 -40 1000

样例输出 #2

-403015.7500000

样例 1 解释：使得联合权值取到最小值的 为 0.5 1 1.5 2 2.5。

数据范围和约定：

对于全部数据，有 ，。

评分规则：

本题使用 Special Judge，如果你的答案是 ，标准答案是 ，则你将获得

分。

每个 Subtask 内捆绑测试。即取 Subtask 内得分最小的作为 Subtask 得分。

题解

分析题目

若a为不减序列

在仅考虑一组数值 a , b 时存在函数   ，其中 a 为定值。根据初中数学二次函数的相关概念可得 

由此我们便可以推广到对于任意不减序列 a 都有唯一确定的不减序列 b 使得联合权值 最小，此时 。

在a的单调性不能保证时

将等式变形，得到

假设一组数据 ， ， ， 满足 且 。  

不难发现此时的联合权值 与 成正相关，由平面间两点距离公式 可得 是点 与点 距离的平方。

因为 且 ，所以点 ，点 分居直线 两侧，因此当点 与点 的连线与直线 垂直，即 时两点距离最小，由此推广到整个序列 a ， b 。此时联合权值 取到最小值。

实现方式

单调栈

由b序列单调不减的特性联想到单调栈，维护一个单调栈，在a序列单调不减时将 作为 入栈，否则不断弹栈至满足单调性，并计算其平均值再入栈。

压缩

不难发现，如果将每一个 作为单独的元素入栈会产生大量相邻的重复元素而造成资源浪费，因此可以使用结构体仅将元素数值和长度入栈。

下附代码

#include<bits/stdc++.h>
using namespace std;
struct Stu{
    int l;
    double x;
}st[1000010];
int n,top;
double ans,ls[1000010];
int a[1000010];
void print()//检查b值是否正确
{
    for(int i=0;i<=top-1;i++)
    {
        cout<<st[i].x<<" "<<st[i].l<<endl;
    }
}
int main()
{
    cin>>n;
    cout<<fixed<<setprecision(7);
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        ls[i]=1.0*a[i]/2;
        if(top==0)
            st[top].l=1,st[top++].x=ls[i];
        else{
            int l=1;
            double sum=ls[i];
            while(sum/l<st[top-1].x&&top!=0)
            {
                l+=st[top-1].l;
                sum+=st[top-1].x*st[top-1].l;
                top--;
            }
            st[top].x=sum/l,st[top++].l=l;
        }
    }
    //print();
    int z=1;
    for(int i=0;i<=top-1;i++)
    {
        for(int j=1;j<=st[i].l;j++)
        {
            ans+=st[i].x*(st[i].x-a[z++]);
        }
    }
    cout<<ans;
    return 0;
 }