2014
03-13

# Star

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.

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.

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.

5 1 2
1 2 3 4 5
6 2 3
6 1 2 4 3 5

Case 1: 4.000
Case 2: 3.800

Problem from:http://acm.hdu.edu.cn/showproblem.php?pid=3276

DP在该处的运用：DP[i]用来存储数列前 i 个数中，所有 长度为Len(x<=Len<=y)的连续子序列 中 最大的Ek(Ek:上一行有定义)

DP前，先用一个数组sum[]，sum[i]存前 i 个数的 Ek

#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
const int MAXN=50010;
int a[MAXN],n,x,y,Case;
double sum[MAXN],Ldp[MAXN],Rdp[MAXN];//sum[i]存前i个数的Ek；Ldp[i]存前i个数中 满足长度的子序列 中的最大Ek；Rdp[i]存第i个数到第n个个数中 满足长度的子序列 中的最大Ek
bool f(double dt){
sum[0]=0;
for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i]-dt;
deque<int> que;
Ldp[x-1]=-1e10;
for(int i=x;i<n-x;i++){//求Ldp[]
while(!que.empty() && sum[i-x]<sum[que.back()])
que.pop_back();
que.push_back(i-x);
while(que.front()<i-y)
que.pop_front();
Ldp[i]=max(Ldp[i-1],sum[i]-sum[que.front()]);
}
que.clear();
sum[n+1]=0;
for(int i=n;i>0;i--)sum[i]=sum[i+1]+a[i]-dt;
Rdp[n-x+2]=-1e10;
for(int i=n-x+1;i>x;i--){//求Rdp[]，原理和求Ldp[]一样
while(!que.empty() && sum[i+x]<sum[que.back()])
que.pop_back();
que.push_back(i+x);
while(que.front()>i+y)
que.pop_front();
Rdp[i]=max(Rdp[i+1],sum[i]-sum[que.front()]);
}
for(int i=x+1;i<=n-x;i++)//枚举判断
if(Ldp[i-1]+Rdp[i+1]>=0)return true;
return false;
}
void work(){
double L=1,R=200000,ans;
while(R-L>1e-5){
ans=(L+R)/2;//二分搜索最大平均值
if(f(ans))L=ans;
else R=ans;
}
printf("Case %d: %.3lf\n",++Case,ans);
}
int main()
{
while(scanf("%d%d%d",&n,&x,&y)!=EOF){
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
work();
}
return 0;
}

View Code

1. 用对＂国奴＂法应对民民主外人？无知、无趣、无羞，丑恶心底暴露无遗，属不打自招，此种小儿科用来＂代表＂政权脸面，何来脸面！

2. 我没看懂题目
2
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5
我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
第二个是7 0 6 -1 1 -6 7输出是14 7 7
不知道题目例子是怎么得出来的

3. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术，也不懂什么是算法，从而也不要求程序员懂什么算法，做程序从来不考虑性能问题，只要页面能显示出来就是好程序，这是国内的现状，很无奈。

4. 网站做得很好看，内容也多，全。前段时间在博客园里看到有人说：网页的好坏看字体。觉得微软雅黑的字体很好看，然后现在这个网站也用的这个字体！nice!