max average problem

see

http://blog.163.com/lfw2565295@126/blog/static/122005162011512103838669/

http://hi.baidu.com/fhnstephen/blog/item/5eae830a3c929f8cd0581b30.html

http://acm.hdu.edu.cn/showproblem.php?pid=2993

参考代码： http://www.cppblog.com/huicpc0860/archive/2010/08/09/122835.html

#include <cstdio>
using namespace std;
#define N 100010
#define max(x,y) ((x)>(y)?(x):(y))
typedef long long  LL;
int s[N];
struct point {
        int x, y;
        point(){}
        point(int x,int y):x(x),y(y){}
}p[N];
point operator - (const point &a, const point &b) { return point(a.x-b.x, a.y-b.y); }
LL operator ^ (const point &a, const point &b) { return (LL)a.x*b.y - (LL)a.y*b.x; }
inline int get(){
        int s=0;
        char c;
        while(c=getchar(),c!=' '&&c!='\n')s=s*10+c-'0';
        return s;
}
int main() {
        int n,k;
        s[0]=0;
        while (~scanf("%d ",&n)){
                k=get();n++;
                for(int i=1;i<n;++i){
                        s[i]=get();
                        s[i]+=s[i-1];
                }
                double ans=0;
                for(int i=k,m=-1,f=0;i<n;++i){
                        point now(i-k,s[i-k]);
                        while(f<m&&(p[m]-p[m-1]^now-p[m-1])<0)--m;
                        p[++m]=now;
                        while(f<m&&(LL)(s[i]-p[f].y)*(i-p[f+1].x)<(LL)(s[i]-p[f+1].y)*(i-p[f].x))f++;
                        ans=max(ans,double(s[i]-p[f].y)/(i-p[f].x));
                }
                printf("%.2lf\n",ans);
        }
}

第三题：园艺布置

近期，百度采纳了员工们的提议，计划在总部大楼内部种植园艺，以提供更加温馨的工作环境。公司将园艺设计的任务交给了度度熊同学。

公司总部大楼内部的构造可以分为n个区域，编号为0, 1, …, n–1，其中区域i与i + 1是相邻的（0 ≤ i < n – 1）。根据员工的投票和反馈，度度熊拿到了一份数据，表明在区域i种植园艺可以获得员工的满意度为Ai。度度熊希望园艺的布置方案满足条件：

1.至少覆盖m个区域；

2.布置园艺的区域是连续的。

请帮他找到一种满足条件的方案，使布置园艺区域的员工的满意度的平均值最大。

输入描述

输入的第一行包含两个整数n和m，分别表示总区域数和至少覆盖的区域数。

第二行包含n个整数A₀,A₁,…,A_{n– 1}，依次表示在每个区域种植园艺可以获得员工的满意度。

输出描述

输出一行，表示员工的平均满意度的最大值。如果这个数是一个整数，则直接按整数格式输出；否则，请用最简分数表示，分子分母以“/”分割，格式见样例。

样例输入1

3 1

2 3 1

样例输入2

5 3

1 8 2 4 8

样例输出1

3

样例输出2

11/2

15

提示

样例2的正确答案为11/2，尽管22/4数值也相同，但由于没有化简，所以是错误的。

对于100%的数据，1 ≤m≤n≤ 10⁶，1 ≤A_i≤ 10⁶。