HDU 4923

题目大意：

　　给出一串序列Ai{0,1}，求一个序列Bi[0,1]（Bi<Bi+1），使得sigama(Ai-Bi)^2最小

思路：

若B相同，则取A的平均数可使方差最小

若B有序，
　　若A==00..011..1序列则 B最优取法为0序列中取0，1序列中取1，满足B1<B2，最优，B1,B2取值互不影响，不考虑

　　若A==11..100..0序列则 B为其平均数，因为最优是B在1序列中取1,0序列中取0，由于B1<B2，故只有当B1=B2时，可使其最优，解得最小为 1的个数sum/总个数len

因此，可以建立单调栈，栈按sum/len单调递增，若新插入10段的sum/len与栈顶比较，若小于栈顶，则合并，否则入栈

#include <cstdio>

#include <cstring>

#include <stack>

using namespace std;

struct Edge{

    int sum,len;

};

int a[];

stack<Edge> q;

int main()

{

    //freopen("1003.in","r",stdin);

    int tt,n;

    scanf("%d",&tt);

    while(tt--)

    {

        scanf("%d",&n);

        for(int i=; i<=n; i++)

            scanf("%d",&a[i]);

        double ans=;

        int l=,r=n;

        while(a[l]==) l++;

        while(a[n]==) n--;

        if(l>n)

        {

            printf("%.6f",0.0);

            continue;

        }

        r=l-;

        while(r<n)

        {

            int sum=;

            while(r+<=n && a[r+]==)

            {

                sum=sum+;

                r++;

            }

            while(r+<=n && a[r+]==)

                r++;

            Edge tmp;

            tmp.sum=sum;

            tmp.len=r-l+;

            while(!q.empty() && 1.0*q.top().sum/q.top().len >= 1.0*tmp.sum/tmp.len)

            {

                tmp.sum+=q.top().sum;

                tmp.len+=q.top().len;

                q.pop();

            }

            q.push(tmp);

            l=r+;

        }

        while(!q.empty())

        {

            int len=q.top().len,sum=q.top().sum;

            ans+=(sum*(1.0-1.0*sum/len)*(1.0-1.0*sum/len)+(len-sum)*(1.0*sum/len)*(1.0*sum/len));

            q.pop();

        }

        printf("%.6f\n",ans);

    }

    return ;

}

巴特西

HDU 4923

最新文章

热门文章