hdu-3276-dp+二分+單調隊列

Star

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 516    Accepted Submission(s): 213

Problem Description

One of Resty's interests is to watch stars. The Stars are so beautiful! Lyra's Vega, Alpha Aquila - Altair and Alpha Cyg consist of the Summer Triangle. Resty likes them very much.

One day, Resty comes to the Moon to have his picnic. Soon he found that he can see so many beautiful stars here! You can never find such a view again - All the beautiful stars are in one line!! So Resty wants to take photos to record the incredible moment.

Resty likes those stars so much so he knows which one is more beautiful. Now he gives each star a score, (a number between 1 and 200000, the higher, the better). So we can use an integer sequence to show the stars from left to right.

Resty's camera is very strange and it will take two photos at one time, and each photo will contain a series of continuous stars in it. No stars will appear in both photos, and even no two stars that adjacent to each other will be in different photos. The number of stars in each photo will between x and y.

Now, Resty tells you the sequence, you must find two photos that the average score of all the stars in the photos is as great as possible.

Input

The input consists of more than one test case.

Process to the END OF DATA.

For each test case:

The first line contains 3 integers: n, x, y. n is the number of stars.

1 <= x < y <= n <=50000

The second line contains n integers (between 1 and 200000), the score of each stars.

Output

You must output the max average score Resty could get with the precision to 3 digits after the decimal point.

Output Format is "Case ID: ANS" one line for each data

Don't print any empty line to the output

Sample Input

5 1 2

1 2 3 4 5

6 2 3

6 1 2 4 3 5

Sample Output

Case 1: 4.000

Case 2: 3.800

Author

Resty

Source

HDOJ Monthly Contest – 2010.01.02

   　　感覺很不錯的一道題。

　　 題意: 從一個序列中找出兩個不相鄰的連續子序列(且每個子序列的長度必須在[x,y]内),使得兩個序列内的數的平均值最大化。

        做法: 二分這個最大值，判定的時候發現這個式子  (s1+s2)/(l1+l2)>=p , s1,s2為兩個序列的總和，l1,l2為長度。轉移一下發現

就是讓序列中的每個數都減去p之後總和仍>=0,想到這就ok了，我們預處理一下數組。然後計算l[i],r[i], l[i]表示在i之前的滿足長度條件的序列的最大值，r[i]同理。然後枚舉中間點，隻要最大值不小于零表示目前的p可行。

　　計算l,r時用到了隊列優化操作。

　　　用到了優先隊列1s+，但是可以用單調隊列優化，明天試試^-^。

1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define inf 0x3f3f3f3f
 4 #define eps 1e-6
 5 int a[50010];
 6 double b[50010],fl[50010],fr[50010];
 7 int n,x,y;
 8 struct node{
 9     int id;
10     double s;
11     bool operator< (const node& tmp)const{
12         return s>tmp.s;
13     }
14 };
15 bool ok(double p){
16     for(int i=1;i<=n;++i){
17         b[i]=b[i-1]+(double)a[i]-p;
18     }
19     b[n+1]=b[n];
20     priority_queue<node>q;
21     fl[0]=-inf;
22     fr[n+1]=-inf;
23     
24     
25     for(int i=1;i<=n;++i){
26         if(i-x>=0) q.push(node{i-x,b[i-x]});
27         fl[i]=fl[i-1];
28         while(!q.empty() && i-q.top().id>y) q.pop();
29         if(!q.empty()){
30             fl[i]=max(fl[i],b[i]-b[q.top().id]);
31         }
32     }
33     while(!q.empty())q.pop();
34     for(int i=n;i>=1;--i){
35         if(i+x<=n+1) q.push(node{i+x,b[n]-b[i+x-1]});
36         fr[i]=fr[i+1];
37         while(!q.empty() && q.top().id-i>y) q.pop();
38         if(!q.empty()){
39             fr[i]=max(fr[i],b[n]-b[i-1]-q.top().s);
40         }
41         //cout<<"fr="<<fr[i]<<endl;
42     }
43     double res=-inf;
44     for(int i=1;i<=n;++i){
45         res=max(res,fl[i-1]+fr[i+1]);
46     }
47     return res>=0;
48 }
49 int main(){
50     int i,j,k,cas=0;
51     while(cin>>n>>x>>y){
52         for(i=1;i<=n;++i) scanf("%d",a+i);
53         double l=1,r=200000;
54         while(fabs(l-r)>eps){
55             double mid=(l+r)/2;
56             if(ok(mid)) l=mid;
57             else r=mid;
58         }
59         printf("Case %d: %.3f\n",++cas,l);
60     }
61     return 0;
62 }