• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            pku 2018 Best Cow Fences 斜率優化,注意中間運算結果超int

            具體分析間NOI論文:
            淺談數形結合思想在信息學競賽中的應用,例題2
            直接貼代碼了。。
            再次注意消除浮點誤差時中間運算結果超出int范圍!!
             1 # include <stdio.h>
             2 # define N 100005
             3 # define less(x1,y1,x2,y2,x3,y3,x4,y4) (y2-y1)*(x4-x3)<=(y4-y3)*(x2-x1)
             4 # define max(a,b) ((a)>(b)?(a):(b))
             5 int data[N],q[N][2],s=-1,e=-1;
             6 int n,f;
             7 int main()
             8 {
             9     int i;
            10     scanf("%d%d",&n,&f);
            11     data[0]=0;
            12     for(i=1;i<=n;i++)
            13     {
            14         scanf("%d",data+i);
            15         data[i]+=data[i-1];
            16     }
            17     e++;
            18     q[e][0]=0;
            19     q[e][1]=0;
            20     double res;
            21     int y=-1,x=-1;
            22     for(i=1;i<=n;i++)
            23     {
            24         while(s+2<=e&&i-q[s+2][0]>=f) s++;
            25         while(e>=s+2&&less(q[e][0],q[e][1],i,data[i],q[e-1][0],q[e-1][1],q[e][0],q[e][1])) e--;
            26         e++;
            27         q[e][0]=i;
            28         q[e][1]=data[i];
            29         if(s<e&&i-q[s+1][0]>=f)
            30             if(y==-1&&x==-1||x!=-1&&y!=-1&&((long long)data[i]-q[s+1][1])*x>(long long)y*(i-q[s+1][0]))
            31                 y=data[i]-q[s+1][1],x=i-q[s+1][0];
            32     }
            33     printf("%d\n",(long long)(y*1000)/x);
            34     return 0;
            35 }


            posted on 2010-11-07 01:53 yzhw 閱讀(285) 評論(0)  編輯 收藏 引用 所屬分類: DP

            <2010年11月>
            31123456
            78910111213
            14151617181920
            21222324252627
            2829301234
            567891011

            導航

            統計

            公告

            統計系統

            留言簿(1)

            隨筆分類(227)

            文章分類(2)

            OJ

            最新隨筆

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            久久精品中文字幕有码| 亚洲精品白浆高清久久久久久| 嫩草伊人久久精品少妇AV| 亚洲AV日韩精品久久久久| 成人国内精品久久久久影院| 久久黄色视频| 麻豆亚洲AV永久无码精品久久| 91精品国产高清久久久久久国产嫩草 | 男女久久久国产一区二区三区| 麻豆亚洲AV永久无码精品久久| 亚洲午夜久久影院| 久久久噜噜噜久久中文字幕色伊伊| 久久久久亚洲AV无码麻豆| 国产免费福利体检区久久| 久久久久亚洲AV无码专区首JN| 亚洲精品高清国产一久久| 精品国产乱码久久久久软件| 99久久精品国内| 亚洲伊人久久精品影院| 久久人人爽人人精品视频| 青青热久久综合网伊人| 日韩人妻无码一区二区三区久久| 久久97久久97精品免视看| 久久综合亚洲欧美成人| 久久婷婷五月综合色奶水99啪| 久久精品视屏| 久久艹国产| 99久久99久久精品国产片果冻| 久久中文骚妇内射| 狠狠色婷婷久久一区二区| 久久久久久久久66精品片| 久久噜噜久久久精品66| 97久久精品人人澡人人爽| 久久久精品午夜免费不卡| 成人久久综合网| 国产激情久久久久影院小草| 国产精品久久久久久搜索 | 97超级碰碰碰久久久久| 久久久久久国产精品免费无码 | 久久偷看各类wc女厕嘘嘘| 久久精品人妻中文系列|