• <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>
            獨立博客: 哲學與程序

            哲學與程序

            ZOJ@3433

            ZOJ@3433
            題意:m個按序迷宮,每個迷宮可收集一定數量的cake,迷宮中的BOSS有n個ice heart,每一個需消耗的一定cake才能獲得,問通過這m個迷宮,可拿多少ice heart。
            解法:貪心。對于一個ice heart,如果當前cake數大于或等于該ice heart的消耗,則直接取得,如果不,則用前面消耗的最大cake的與當前ice heart比較,當前ice heart消耗小些,則交換,賺一點cake,否則不換。用一個最大堆維護即可。
            // 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 哲學與程序 閱讀(197) 評論(0)  編輯 收藏 引用 所屬分類: Algorithm

            導航

            公告

            歡迎訪問 http://zhexue.sinaapp.com

            常用鏈接

            隨筆分類(37)

            隨筆檔案(41)

            Algorithm

            最新隨筆

            搜索

            最新評論

            獨立博客: 哲學與程序
            久久久久久久人妻无码中文字幕爆| …久久精品99久久香蕉国产| 狠狠色综合久久久久尤物| 国产美女久久精品香蕉69| 狠狠久久亚洲欧美专区| 精品久久久久久无码中文字幕| 亚洲国产精品综合久久一线| 久久综合综合久久综合| 精品国产青草久久久久福利 | 污污内射久久一区二区欧美日韩 | 国产精品无码久久综合| 国产激情久久久久影院小草| 精品久久久久成人码免费动漫| 久久天堂AV综合合色蜜桃网| 久久久久国色AV免费看图片| 午夜精品久久久久久久| 久久精品一区二区国产| 色婷婷久久综合中文久久一本| 亚洲AV日韩精品久久久久久久| 国产三级精品久久| 国产精品99久久免费观看| 久久午夜福利无码1000合集| 99久久精品国产毛片| 久久A级毛片免费观看| 久久久亚洲裙底偷窥综合| 国产亚洲精久久久久久无码AV| 色综合久久中文字幕无码| 久久综合亚洲色HEZYO社区| 国产69精品久久久久9999| 成人国内精品久久久久一区| 久久久久久久久久久| 合区精品久久久中文字幕一区| 国产精品日韩欧美久久综合| 热久久这里只有精品| 久久久久四虎国产精品| 久久久久中文字幕| 99久久夜色精品国产网站| 成人精品一区二区久久| 99久久亚洲综合精品网站| 久久99国产精品成人欧美| 国内精品久久久久久久久电影网|