首页 > 代码库 > HDU 4923

HDU 4923

2024-07-16 09:31:53   218人阅读

题目大意：

　　给出一串序列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[1000005];stack<Edge> q;int main(){    //freopen("1003.in","r",stdin);    int tt,n;    scanf("%d",&tt);    while(tt--)    {        scanf("%d",&n);        for(int i=1; i<=n; i++)            scanf("%d",&a[i]);        double ans=0;        int l=1,r=n;        while(a[l]==0) l++;        while(a[n]==1) n--;        if(l>n)        {            printf("%.6f",0.0);            continue;        }        r=l-1;        while(r<n)        {            int sum=0;            while(r+1<=n && a[r+1]==1)            {                sum=sum+1;                r++;            }            while(r+1<=n && a[r+1]==0)                r++;            Edge tmp;            tmp.sum=sum;            tmp.len=r-l+1;            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+1;        }        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 0;}
View Code

 


联系
我们