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

            學(xué)習(xí)心得(code)

            superlong@CoreCoder

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

            公告

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

            常用鏈接

            留言簿(4)

            我參與的團(tuán)隊(duì)

            搜索

            •  

            最新隨筆

            最新評(píng)論

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

            閱讀排行榜

            評(píng)論排行榜

            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

            一個(gè)不完全背包,簡(jiǎn)單貪心,對(duì)fammer信息按price從小到大排序,
            然后裝進(jìn)背包求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);
            }
            優(yōu)化:以上為O(n*LOG(n)),因?yàn)閜rice的范圍比較小,可以用一個(gè)
            hash[i]表示price為i的數(shù)量,然后線性的掃一遍就好了(類似桶排序吧)
            于是優(yōu)化到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 閱讀(374) 評(píng)論(0)  編輯 收藏 引用 所屬分類: USACO
            久久av无码专区亚洲av桃花岛| 久久99精品久久久大学生| 精品久久久久久无码中文字幕一区| 久久精品aⅴ无码中文字字幕重口 久久精品a亚洲国产v高清不卡 | 日日噜噜夜夜狠狠久久丁香五月| 国产呻吟久久久久久久92| 狠狠色婷婷综合天天久久丁香 | 久久99精品久久久久久动态图| 国产精品久久久久久久久鸭| 麻豆久久| 久久免费视频观看| 久久久久久久波多野结衣高潮 | 日本久久久久亚洲中字幕| 亚洲一区中文字幕久久| 久久夜色精品国产亚洲| 国内精品久久久久久久久电影网| 99久久国产亚洲综合精品| 国产精品9999久久久久| 伊人久久大香线蕉无码麻豆| 狠狠色婷婷综合天天久久丁香| 18岁日韩内射颜射午夜久久成人| 久久99国产精品久久99| 久久亚洲中文字幕精品有坂深雪 | 国内精品久久久久久麻豆| 久久久精品人妻一区二区三区四 | 精品一二三区久久aaa片| 久久精品国产一区二区| 亚洲国产精品热久久| 国产亚洲欧美精品久久久| 97久久国产综合精品女不卡| 久久综合偷偷噜噜噜色| 亚洲国产精品成人久久蜜臀| 91久久精品国产免费直播| 久久国产精品99久久久久久老狼| 久久精品无码专区免费青青| 人妻无码精品久久亚瑟影视| 亚洲精品高清一二区久久| 女人高潮久久久叫人喷水| 久久无码AV一区二区三区| 狠狠色婷婷久久综合频道日韩| 久久久久久久女国产乱让韩|