302 - 最大平均值

Sylveon

原題：http://hoj.twbbs.org/judge/problem/view/302
AC：http://hoj.twbbs.org/judge/judge/submission/17485

大家都做O(nlogn)的，我偏要做O(n)的斜率優化，作法參考這中國國家代表隊論文 (HOJ)，基本上是做了「數形」結合的概念轉化為一斜率極值問題來做。

#ifdef DBG

#include<conio.h>

#define pause() getch()

#else

#define pause()

#endif

#include<cstdio>

#include<iostream>

#include<deque>

#include<algorithm>

using namespace std;

typedef long long ll;

typedef pair<ll,ll> pii;

#define mp(X,Y) make_pair((X),(Y))

ll sum[100001]={0};;

int N,F;

deque<pii> dq;

inline int cross(pii a,pii b,pii c)

{

        return (b.first-a.first)*(c.second-b.second)-(b.second-a.second)*(c.first-b.first);

}

void push(pii p)

{

        while(dq.size()>1)

        {

                pii &m=dq[0];

                pii &b=dq[1];

                if(cross(b,m,p)<=0)

                        dq.pop_front();

                else

                        break;

        }

        dq.push_front(p);

}

bool next_is_better(pii pt)

{

        pii &b=dq.back();

        pii &b2=*(dq.rbegin()+1);

        //double k1=(double)(pt.second-b.second)/(pt.first-b.first);

        //double k2=(double)(pt.second-b2.second)/(pt.first-b2.first);

        return (pt.second-b.second)*(pt.first-b2.first)<(pt.second-b2.second)*(pt.first-b.first);

        //return k1<k2;

       

}

int main()

{

        ll ans=0;

        scanf("%d%d",&N,&F);

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

        {

                scanf("%lld",&sum[i]);

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

        }

        for(int i=F;i<=N;++i)

        {

                push(mp(i-F,sum[i-F]));

                while(dq.size()>1&&next_is_better(mp(i,sum[i])))dq.pop_back();

                ans=max(ans,(dq.back().second-sum[i])/(dq.back().first-i));

        }

        printf("%lld\n",ans);

       

        return 0;

}