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

            學習心得(code)

            superlong@CoreCoder

              C++博客 :: 首頁 :: 聯系 :: 聚合  :: 管理
              74 Posts :: 0 Stories :: 5 Comments :: 0 Trackbacks

            公告

            文字可能放在http://blog.csdn.net/superlong100,此處存放代碼

            常用鏈接

            留言簿(4)

            我參與的團隊

            搜索

            •  

            最新隨筆

            最新評論

            • 1.?re: Poj 1279
            • 對于一個凹多邊形用叉積計算面積 后能根據結果的正負來判斷給的點集的時針方向?
            • --bsshanghai
            • 2.?re: Poj 3691
            • 你寫的這個get_fail() 好像并是真正的get_fail,也是說fail指向的串并不是當前結點的子串。為什么要這樣弄呢?
            • --acmer1183
            • 3.?re: HDU2295[未登錄]
            • 這個是IDA* 也就是迭代加深@ylfdrib
            • --superlong
            • 4.?re: HDU2295
            • 評論內容較長,點擊標題查看
            • --ylfdrib
            • 5.?re: HOJ 11482
            • 呵呵..把代碼發在這里很不錯..以后我也試試...百度的編輯器太爛了....
            • --csuft1

            閱讀排行榜

            評論排行榜

            Mixing Milk

            Since milk packaging is such a low margin business, it is important to keep the price of the raw product (milk) as low as possible. Help Merry Milk Makers get the milk they need in the cheapest possible manner.

            The Merry Milk Makers company has several farmers from which they may buy milk, and each one has a (potentially) different price at which they sell to the milk packing plant. Moreover, as a cow can only produce so much milk a day, the farmers only have so much milk to sell per day. Each day, Merry Milk Makers can purchase an integral amount of milk from each farmer, less than or equal to the farmer's limit.

            Given the Merry Milk Makers' daily requirement of milk, along with the cost per gallon and amount of available milk for each farmer, calculate the minimum amount of money that it takes to fulfill the Merry Milk Makers' requirements.

            Note: The total milk produced per day by the farmers will be sufficient to meet the demands of the Merry Milk Makers.

            PROGRAM NAME: milk

            INPUT FORMAT

            Line 1: Two integers, N and M.
            The first value, N, (0 <= N <= 2,000,000) is the amount of milk that Merry Milk Makers' want per day. The second, M, (0 <= M <= 5,000) is the number of farmers that they may buy from.
            Lines 2 through M+1: The next M lines each contain two integers, Pi and Ai.
            Pi (0 <= Pi <= 1,000) is price in cents that farmer i charges.
            Ai (0 <= Ai <= 2,000,000) is the amount of milk that farmer i can sell to Merry Milk Makers per day.

            SAMPLE INPUT (file milk.in)

            100 5
            5 20
            9 40
            3 10
            8 80
            6 30

            OUTPUT FORMAT

            A single line with a single integer that is the minimum price that Merry Milk Makers can get their milk at for one day.

            SAMPLE OUTPUT (file milk.out)

            630

            一個不完全背包,簡單貪心,對fammer信息按price從小到大排序,
            然后裝進背包求minnum price就好了。
            代碼:
            /*
            ID: superlo1
            LANG: C++
            TASK: milk
            */

            #include 
            <iostream>
            #include 
            <algorithm>
            using namespace std;

            struct node
            {
                
            int p, a;
            }fam[
            5001];

            bool cmp(node a,node b)
            return a.p < b.p; }

            int n, m;

            int main()
            {
                freopen(
            "milk.in","r",stdin);
                freopen(
            "milk.out","w",stdout);
                scanf(
            "%d %d"&n, &m);
                
            int i;
                
            for(i = 0; i < m; i ++)
                    scanf(
            "%d %d"&fam[i].p, &fam[i].a);
                sort( fam, fam 
            + m, cmp);
                
            int ans = 0;
                i 
            = 0;
                
            while(n)
                {
                    
            if( n > fam[i].a)
                    {
                        n 
            -= fam[i].a;
                        ans 
            += fam[i].p * fam[i].a;
                    }
                    
            else
                    {
                        ans 
            += n * fam[i].p;
                        n 
            = 0;
                    }
                    i 
            ++;
                }
                printf(
            "%d\n",ans);
                
            //while(1);
            }
            優化:以上為O(n*LOG(n)),因為price的范圍比較小,可以用一個
            hash[i]表示price為i的數量,然后線性的掃一遍就好了(類似桶排序吧)
            于是優化到O(n)。
            代碼:
            #include <fstream>
            #define MAXPRICE 1001
            using namespace std;

            int main() {
                ifstream fin (
            "milk.in");
                ofstream fout (
            "milk.out");
                unsigned 
            int i, needed, price, paid, farmers, amount, milk[MAXPRICE];
                paid 
            = 0;
                fin
            >>needed>>farmers;
                
            for(i = 0;i<farmers;i++){
                    fin
            >>price>>amount;
                    milk[price] 
            += amount;   
                } 
                
            for(i = 0; i<MAXPRICE && needed;i++){
                    
            if(needed> = milk[i]) {
                        needed 
            -= milk[i];
                        paid 
            += milk[i] * i;
                    } 
            else if(milk[i][0]>0) {
                        paid 
            += i*needed;
                        needed 
            = 0;     
                    }
                }
                fout 
            << paid << endl; 
                
            return 0;
            }


            posted on 2009-08-05 00:53 superlong 閱讀(372) 評論(0)  編輯 收藏 引用 所屬分類: USACO
            99久久国产综合精品五月天喷水 | 麻豆成人久久精品二区三区免费| 久久久久无码中| 久久综合久久性久99毛片| 久久亚洲AV无码精品色午夜麻豆| 人妻少妇久久中文字幕| 99久久精品免费国产大片| 日韩久久无码免费毛片软件 | 狠狠色综合网站久久久久久久| 久久精品亚洲福利| 亚洲AV日韩精品久久久久久| 婷婷久久综合九色综合98| 亚洲国产成人久久一区WWW| 久久久久亚洲av无码专区导航| 国产精品亚洲综合专区片高清久久久| 武侠古典久久婷婷狼人伊人| 国产精品国色综合久久| 久久91精品国产91久| 91久久香蕉国产熟女线看| 97久久国产露脸精品国产| 国内精品久久久久久久亚洲| 无码专区久久综合久中文字幕| 久久国产高清一区二区三区| 韩国无遮挡三级久久| 久久久久成人精品无码中文字幕| 国产精品久久新婚兰兰| 久久免费观看视频| 久久久WWW免费人成精品| 久久亚洲综合色一区二区三区| 少妇人妻88久久中文字幕| 精品久久久无码21p发布| 亚洲国产日韩欧美综合久久| 久久久99精品成人片中文字幕 | 乱亲女H秽乱长久久久| 伊人伊成久久人综合网777| 国产福利电影一区二区三区久久老子无码午夜伦不 | 亚洲精品成人久久久| 久久久久亚洲精品中文字幕| 韩国三级中文字幕hd久久精品 | 久久久久av无码免费网| 久久只这里是精品66|