• <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>
            獨(dú)立博客: 哲學(xué)與程序

            哲學(xué)與程序

            ZOJ@3433

            ZOJ@3433
            題意:m個(gè)按序迷宮,每個(gè)迷宮可收集一定數(shù)量的cake,迷宮中的BOSS有n個(gè)ice heart,每一個(gè)需消耗的一定cake才能獲得,問(wèn)通過(guò)這m個(gè)迷宮,可拿多少ice heart。
            解法:貪心。對(duì)于一個(gè)ice heart,如果當(dāng)前cake數(shù)大于或等于該ice heart的消耗,則直接取得,如果不,則用前面消耗的最大cake的與當(dāng)前ice heart比較,當(dāng)前ice heart消耗小些,則交換,賺一點(diǎn)cake,否則不換。用一個(gè)最大堆維護(hù)即可。
            // 2386805      2011-01-15 21:33:57        Accepted      3433      C++      350      4100      redsea
            #include<stdio.h>
            #include
            <string.h>
            #include
            <stdlib.h>
            #include
            <algorithm>
            #include
            <queue>
            using namespace std;
            struct laby
            {
                
            int n;
                
            int cake;
                
            int sp[1001];
            }l[
            1001];
            int m;
            struct Node
            {
                
            int cake;
                
            bool operator < (struct Node a)const
                {
                    
            return cake < a.cake;
                }
            };
            void solve()
            {
                priority_queue
            <struct Node>Heap;
                
            struct Node tmp;
                
            int cake = 0;
                
            int ans = 0;
                
            for(int i = 1; i <= m; i++)
                {
                    cake 
            += l[i].cake;
                    
            for(int j = 0; j < l[i].n; j++)
                    {
                        
            if(cake >= l[i].sp[j])
                        {
                            ans
            ++;
                            cake 
            -= l[i].sp[j];
                            tmp.cake 
            = l[i].sp[j];
                            Heap.push(tmp);
                        }
            else{
                            
            if(!Heap.empty())
                            {
                                tmp 
            = Heap.top();
                                
            if(tmp.cake > l[i].sp[j]){
                                    cake 
            += tmp.cake;
                                    ans
            --;
                                    Heap.pop();
                                }
                            }
                            
            if(cake >= l[i].sp[j])
                            {
                                ans
            ++;
                                cake 
            -= l[i].sp[j];
                                tmp.cake 
            = l[i].sp[j];
                                Heap.push(tmp);
                            }
                        }
                    }
                }
                printf(
            "%d\n",ans);    
            }
            int main()
            {
                
            int T;
                scanf(
            "%d",&T);
                
            while(T--)
                {
                    scanf(
            "%d",&m);
                    
            for(int i = 1; i <= m; i++){
                        scanf(
            "%d",&l[i].n);
                        
            for(int j = 0; j < l[i].n; j++){
                            scanf(
            "%d",&l[i].sp[j]);
                        }
                    }
                    
            for(int i = 1; i <= m; i++)
                    {
                        scanf(
            "%d",&l[i].cake);
                    }
                    solve();
                }
                
            return 0;
            }


            posted on 2011-01-15 21:44 哲學(xué)與程序 閱讀(195) 評(píng)論(0)  編輯 收藏 引用 所屬分類(lèi): Algorithm

            導(dǎo)航

            公告

            歡迎訪問(wèn) http://zhexue.sinaapp.com

            常用鏈接

            隨筆分類(lèi)(37)

            隨筆檔案(41)

            Algorithm

            最新隨筆

            搜索

            最新評(píng)論

            獨(dú)立博客: 哲學(xué)與程序
            国产—久久香蕉国产线看观看 | 一本一道久久精品综合| 久久久久国产精品熟女影院| 国内精品久久久久影院免费| 久久中文娱乐网| 久久99国产精品久久99小说| 狠狠88综合久久久久综合网| 久久精品国产99久久香蕉| 久久精品国产亚洲AV影院| 国产亚洲婷婷香蕉久久精品| 久久只有这精品99| 99久久精品费精品国产一区二区 | 91精品国产91久久久久福利| 精品多毛少妇人妻AV免费久久| 亚洲欧美国产精品专区久久| 91精品国产综合久久香蕉| 伊人久久大香线蕉亚洲五月天| 国产精品美女久久久久av爽| 久久香蕉超碰97国产精品| 久久久久亚洲精品男人的天堂 | 伊人久久大香线蕉av不变影院| 国产成人香蕉久久久久| 日韩AV无码久久一区二区| 久久久久国产亚洲AV麻豆| 久久久91精品国产一区二区三区| 亚洲中文字幕久久精品无码APP | 国产99久久久国产精免费| 色偷偷久久一区二区三区| 色婷婷综合久久久久中文字幕| 丁香久久婷婷国产午夜视频| 国产精品一区二区久久精品| 久久久亚洲欧洲日产国码aⅴ | 亚洲午夜久久久久妓女影院| 亚洲国产成人久久笫一页| 久久男人AV资源网站| 少妇久久久久久被弄到高潮| 国产午夜福利精品久久| 国产精品成人久久久久久久| 久久成人18免费网站| 欧美亚洲日本久久精品| 欧美伊人久久大香线蕉综合69|