HDU 2993 MAX Average Problem(スロープ最適化DP)

MAX Average Problem
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 3521    Accepted Submission(s): 896
Problem Description
Consider a simple sequence which only contains positive integers as a1, a2 ... an, and a number k. Define ave(i,j) as the average value of the sub sequence ai ... aj, i<=j. Let’s calculate max(ave(i,j)), 1<=i<=j-k+1<=n.
 
 
Input
There multiple test cases in the input, each test case contains two lines.
The first line has two integers, N and k (k<=N<=10^5).
The second line has N integers, a1, a2 ... an. All numbers are ranged in [1, 2000].
 
 
Output
For every test case, output one single line contains a real number, which is mentioned in the description, accurate to 0.01.
 
 
Sample Input
10 6 6 4 2 10 3 8 5 9 4 1
 
 
Sample Output
6.50
 
 
Source
2009 Multi-University Training Contest 19 - Host by BNU
 
 
Recommend
chenrui
 
 
本題の比較2のところは自分で入力関数を書くので、scanfでタイムアウトします.のこれも良い最適化方法のようですが、仕方がないときは試してみてくださいね.
 
 
長さnのシーケンスが与えられ、連続した長さがmより大きいサブシーケンスがサブシーケンスの平均値を最小にする.
 
詳細は以下を参照してください.
NOI 2004年周源の論文『
数形結合思想の情報学コンテストにおける応用を浅く述べる。 》,
 
 
やり方はネット上の他の人を参考にして、単調なキューでメンテナンスして、以下のコード1のようです.
しかし、結果には影響しませんが、問題があります.
この問題はすでに指摘されています.
http://hi.baidu.com/lccycc_acm/item/e05b5b85c9b27a1fc31627bf
この問題はまさに私が長い間悩んでいたのだ.
後で2点で点を探すのを見て、コード2のような厳密なやり方だと感じました.
 
コード1:

#include<stdio.h>

#include<iostream>

#include<string.h>

#include<queue>

#include<algorithm>

using namespace std;

const int MAXN=100010;

double sum[MAXN];

int a[MAXN];

int q[MAXN];

int head,tail;



double max(double a,double b)

{

    if(a>b)return a;

    else return b;

}



double getUP(int i,int j)//i>j

{

    return sum[i]-sum[j];

}

int getDOWN(int i,int j)

{

    return i-j;

}







int input()

{

    char ch=' ';

    while(ch<'0'||ch>'9')ch=getchar();

    int x=0;

    while(ch<='9'&&ch>='0')x=x*10+ch-'0',ch=getchar();

    return x;

}



int main()

{

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

    //freopen("out.txt","w",stdout);

    int n,k;

    while(scanf("%d%d",&n,&k)!=EOF)

    {

        sum[0]=0;

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

        {

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

           a[i]=input();

            sum[i]=sum[i-1]+a[i];

        }

        head=tail=0;

        q[tail++]=0;

        double ans=0;

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

        {

            while(head+1<tail&&getUP(i,q[head])*getDOWN(i,q[head+1])<=getUP(i,q[head+1])*getDOWN(i,q[head]))

              head++;

            ans=max(ans,getUP(i,q[head])/getDOWN(i,q[head]));



            int j=i-k+1;

            while(head+1<tail&&getUP(j,q[tail-1])*getDOWN(q[tail-1],q[tail-2])<=getUP(q[tail-1],q[tail-2])*getDOWN(j,q[tail-1]))

                 tail--;

            q[tail++]=j;



        }

        printf("%.2lf
",ans);

    }

    return 0;

}

 
 
コード2:

#include<stdio.h>

#include<iostream>

#include<string.h>

#include<queue>

#include<algorithm>

using namespace std;

const int MAXN=100010;



int sum[MAXN];

int q[MAXN];

int top;



long long cross(int a,int b,int c)

{

    long long x1=b-a;

    long long y1=sum[b]-sum[a];

    long long x2=c-b;

    long long y2=sum[c]-sum[b];

    return x1*y2-y1*x2;

}

int bsearch(int l,int r,int i)

{

    while(l<r)

    {

        int mid=(l+r)>>1;

        if(cross(q[mid],q[mid+1],i)<0)r=mid;

        else l=mid+1;

    }

    return l;

}





int input()

{

    char ch=' ';

    while(ch<'0'||ch>'9')ch=getchar();

    int x=0;

    while(ch<='9'&&ch>='0')x=x*10+ch-'0',ch=getchar();

    return x;

}

int main()

{

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

   // freopen("out.txt","w",stdout);

    int n,k;

    while(scanf("%d%d",&n,&k)!=EOF)

    {

        top=0;

        sum[0]=0;

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

        {

            sum[i]=input();

            sum[i]+=sum[i-1];

        }

        double ans=0;

        q[top++]=0;

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

        {

            int j=i-k;

            while(top>1&&cross(q[top-2],q[top-1],j)<0)top--;

            q[top++]=j;

            int temp=bsearch(0,top-1,i);

            double f=((double)(sum[i]-sum[q[temp]]))/(i-q[temp]);

            if(f>ans)ans=f;

        }

        printf("%.2lf
",ans);

    }

    return 0;

}