MAX Average Problem

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5825 Accepted Submission(s): 1446

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 

直接斜率DP:O(N)

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #define INF 99999999typedef long long LL;using namespace std;const int MAX=100000+10;int n,k;int s[MAX],q[MAX];double dp[MAX],sum[MAX];double GetY(int i,int j){ return sum[i]-sum[j];}int GetX(int i,int j){ return i-j;}double DP(){ int head=0,tail=1; q[head]=0; double ans=0; for(int i=1;i<=n;++i)sum[i]=sum[i-1]+s[i]*1.0; for(int i=k;i<=n;++i){ int j=i-k; while(head+1
               
                '9')ch=getchar(); while(ch>='0' && ch<='9')num=num*10+ch-'0',ch=getchar(); return num;}int main(){ while(~scanf("%d%d",&n,&k)){ for(int i=1;i<=n;++i)s[i]=input(); printf("%0.2lf\n",DP()); } return 0;}斜率DP+二分查找:#include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      #include 
                      
                       #include 
                       
                        #include 
                        #include 
                         
                          #define INF 99999999typedef long long LL;using namespace std;const int MAX=100000+10;int n,k;int s[MAX],q[MAX];LL sum[MAX];LL GetY(int i,int j){ return sum[i]-sum[j];}int GetX(int i,int j){ return i-j;}LL check(int mid,int i){ return GetY(i,q[mid+1])*GetX(q[mid+1],q[mid])-GetY(q[mid+1],q[mid])*GetX(i,q[mid+1]);}int search(int l,int r,int i){ //由于斜率单调递增 /*int top=r; while(l<=r){//依据i与mid的斜率 和 i与mid+1的斜率之差求切点 if(l == r && l == top)return q[l];//这里一定要注意假设切点是最后一个点须要另判,由于mid+1不存在会出错 int mid=(l+r)>>1; if(check(mid,i)<0)r=mid-1; else l=mid+1; }*/ while(l
                          
                           >1; if(check(mid,i)<0)r=mid; else l=mid+1; } return q[l];}double DP(){ int head=0,tail=1,p; q[head]=0; double ans=0,dp; for(int i=1;i<=n;++i)sum[i]=sum[i-1]+s[i]; for(int i=k;i<=n;++i){ int j=i-k; while(head+1
                           
                            ans)ans=dp; } return ans;}int input(){//加速外挂 char ch=' '; int num=0; while(ch<'0' || ch>'9')ch=getchar(); while(ch>='0' && ch<='9')num=num*10+ch-'0',ch=getchar(); return num;}int main(){ while(~scanf("%d%d",&n,&k)){ for(int i=1;i<=n;++i)s[i]=input(); printf("%0.2lf\n",DP()); } return 0;}