竹園論壇

標題: 302 - 最大平均值 [打印本頁]

作者: Sylveon    時間: 2014-5-19 22:30
標題: 302 - 最大平均值
原題: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;
  • }








  • 歡迎光臨 竹園論壇 (http://forum.tfcis.org/) Powered by Discuz! X3.2