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

            USACO 1.3 Barn Repair

            題目鏈接:http://ace.delos.com/usacoprob2?a=h9vkjno3LrX&S=barn1

            如果只能使用一塊木板,那就要從第一個(gè)有奶牛的stall到最后一個(gè)有奶牛的stall.
            因?yàn)檫@一塊長(zhǎng)木板中間,可能會(huì)有空的stall,所以會(huì)浪費(fèi)了木板.
            如果可以使用兩塊木板,我們就可以在這塊長(zhǎng)木板中間挖一個(gè)洞,這樣木板總長(zhǎng)度就減小了這個(gè)洞的長(zhǎng)度.
            很明顯,要木板總長(zhǎng)度最小,就挖掉最大的那個(gè)洞.
            能購(gòu)買(mǎi)m塊木板,也就是說(shuō)可以挖m-1個(gè)洞.將洞的長(zhǎng)度從大到小排序,挖掉最大的m-1個(gè)洞即可.

            #include <iostream>
            #include 
            <fstream>
            #include 
            <vector>

            using namespace std;

            ifstream fin(
            "barn1.in");
            ofstream fout(
            "barn1.out");

            #ifdef _DEBUG
            #define out cout
            #define in cin
            #else
            #define out fout
            #define in fin
            #endif

            void solve()
            {
                
            int m,s,c;

                
            in>>m>>s>>c;

                
            //v保存有牛的stall
                vector<int> v(c);

                
            for(int i=0;i<c;++i)
                    
            in>>v[i];

                sort(v.begin(),v.end());

                
            // space保存所有的洞
                vector<int> space;

                
            for(int i=1;i<c;++i){
                    
            if(v[i]-v[i-1]-1!=0){
                        space.push_back(v[i]
            -v[i-1]-1);
                    }
                }

                sort(space.begin(),space.end(),greater
            <int>());

                 
            //由于v的大小>=1。v==1的時(shí)候仍然成立
                int total_len = v[v.size()-1]-v[0]+1;
                
                m
            -=1;

                
            for(int i=0;i<space.size();++i){
                    
            if(m>0){
                        total_len 
            -=space[i];
                        m
            --;
                    }
                }

                
            out<<total_len<<endl;
            }

            int main(int argc,char *argv[])
            {
              solve();
              
            return 0;
            }


            posted on 2009-06-06 11:48 YZY 閱讀(1216) 評(píng)論(3)  編輯 收藏 引用 所屬分類(lèi): AlgorithmUSACO

            評(píng)論

            # re: USACO 1.3 Barn Repair 2009-07-26 11:22 ouyangyuanling

            這個(gè)題目為什么不能直接將每個(gè)空白的間隙從小到大排序,然后取m個(gè)最小的長(zhǎng)度再加上連接不是空白的牛棚數(shù)啊???  回復(fù)  更多評(píng)論   

            # re: USACO 1.3 Barn Repair[未登錄](méi) 2009-07-26 20:08 YZY

            這樣不能保證最多用m塊板子吧  回復(fù)  更多評(píng)論   

            # re: USACO 1.3 Barn Repair 2009-07-26 22:18 ouyangyuanling

            沒(méi)有啊,好想也可以的吧,就是太麻煩了。要判斷的東西變多了。照大多數(shù)人這樣的思路是變的簡(jiǎn)單了問(wèn)題  回復(fù)  更多評(píng)論   

            導(dǎo)航

            <2009年6月>
            31123456
            78910111213
            14151617181920
            21222324252627
            2829301234
            567891011

            統(tǒng)計(jì)

            常用鏈接

            留言簿(2)

            隨筆分類(lèi)

            隨筆檔案

            搜索

            積分與排名

            最新評(píng)論

            閱讀排行榜

            精品永久久福利一区二区| 中文成人无码精品久久久不卡 | 国产高潮国产高潮久久久91| 国产一区二区三区久久精品| 91精品日韩人妻无码久久不卡| 欧美日韩成人精品久久久免费看| 亚洲国产精品无码久久SM| 欧美综合天天夜夜久久| 模特私拍国产精品久久| 九九久久99综合一区二区| 久久亚洲sm情趣捆绑调教| 久久久久久综合一区中文字幕 | 久久精品成人欧美大片| 国产精品亚洲美女久久久| 国内精品久久久人妻中文字幕| 久久99精品九九九久久婷婷| 亚洲精品乱码久久久久久按摩| 激情久久久久久久久久| 久久99久久99小草精品免视看| 亚洲日本久久久午夜精品| 久久91综合国产91久久精品| 麻豆AV一区二区三区久久| 怡红院日本一道日本久久| 久久久无码人妻精品无码| 久久精品国产免费观看 | 99久久精品国产高清一区二区| 伊人久久国产免费观看视频| 久久99精品久久久久久秒播| 久久美女网站免费| 久久久久久亚洲AV无码专区| 亚洲日韩中文无码久久| 亚洲精品无码久久一线| 模特私拍国产精品久久| 狠狠色丁香久久婷婷综合蜜芽五月| 国产精品欧美久久久久无广告 | 香蕉久久AⅤ一区二区三区| 久久久久亚洲?V成人无码| 大蕉久久伊人中文字幕| 精品久久人人爽天天玩人人妻| segui久久国产精品| 精品无码久久久久久久久久|