• <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

            最新隨筆

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            人妻无码久久精品| 久久99精品久久久久久hb无码 | 久久91精品国产91久久麻豆| 久久无码AV中文出轨人妻| 欧美精品一区二区精品久久| 99久久99这里只有免费的精品| 久久精品中文字幕一区| 伊人情人综合成人久久网小说| 久久se精品一区精品二区国产 | 亚洲精品无码久久千人斩| 一本色道久久88综合日韩精品| 久久强奷乱码老熟女| 欧美久久一级内射wwwwww.| 免费一级做a爰片久久毛片潮| 久久久久亚洲?V成人无码| 88久久精品无码一区二区毛片| 91精品免费久久久久久久久| 国产精品久久久久久久久久免费| 国产精品综合久久第一页| 久久精品无码av| 欧美黑人激情性久久| 久久综合给合久久狠狠狠97色| 精品久久8x国产免费观看| 色综合久久久久网| 久久大香萑太香蕉av| 无码人妻少妇久久中文字幕蜜桃| 国产精品久久久久无码av| 国产99久久久久久免费看| 久久久久久免费视频| 久久精品无码一区二区无码| 久久国产免费直播| 久久久久亚洲AV无码专区首JN| 久久99久久99精品免视看动漫| 久久99精品久久久久久野外| 精品伊人久久大线蕉色首页| 国产精品一久久香蕉国产线看观看| 99久久国产免费福利| 亚洲AV无码久久精品成人| 国产91色综合久久免费| 亚洲国产天堂久久综合| 伊人久久综在合线亚洲2019 |