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

            QuXiao

            每天進步一點點!

              C++博客 :: 首頁 :: 新隨筆 :: 聯(lián)系 :: 聚合  :: 管理 ::
              50 隨筆 :: 0 文章 :: 27 評論 :: 0 Trackbacks
            題目來源:

            PKU 1018 Communication System

             

            算法分類:

            枚舉+貪心

             

            原文:

            Communication System

            Time Limit:1000MS  Memory Limit:10000K

            Description

            We have received an order from Pizoor Communications Inc. for a special communication system. The system consists of several devices. For each device, we are free to choose from several manufacturers. Same devices from two manufacturers differ in their maximum bandwidths and prices.
            By overall bandwidth (B) we mean the minimum of the bandwidths of the chosen devices in the communication system and the total price (P) is the sum of the prices of all chosen devices. Our goal is to choose a manufacturer for each device to maximize B/P.

            Input

            The first line of the input file contains a single integer t (1 ≤ t ≤ 10), the number of test cases, followed by the input data for each test case. Each test case starts with a line containing a single integer n (1 ≤ n ≤ 100), the number of devices in the communication system, followed by n lines in the following format: the i-th line (1 ≤ i ≤ n) starts with mi (1 ≤ mi ≤ 100), the number of manufacturers for the i-th device, followed by mi pairs of positive integers in the same line, each indicating the bandwidth and the price of the device respectively, corresponding to a manufacturer.

            Output

            Your program should produce a single line for each test case containing a single number which is the maximum possible B/P for the test case. Round the numbers in the output to 3 digits after decimal point.

            Sample Input

            1 3

            3 100 25 150 35 80 25

            2 120 80 155 40

            2 100 100 120 110

             

            Sample Output

            0.649

             

            Source

            Tehran 2002, First Iran Nationwide Internet Programming Contest

             

             

            中文描述:

            你需要購買n種設(shè)備來組一個通信系統(tǒng),每一種設(shè)備,又是由一些不同的制造商生產(chǎn)的,不同制造商生產(chǎn)的同種設(shè)備會有不同的帶寬和價格。現(xiàn)在你要在每一個設(shè)備的制造商中選一個,使得購買的n種設(shè)備,它們帶寬的最小值與價格之和的比最大。

             

            題目分析:

            一開始想到的就是暴搜,但是搜索的深度達到100,時間肯定是不允許的。想要解決這題,必須找到一個好的查找策略。再想想看這題的特點,最后的答案,帶寬是選取所有設(shè)備中的最小值,而價格是選取所有設(shè)備的價格總和。如果某個制造商生產(chǎn)的某種設(shè)備,它的帶寬較高而價格較低,那么選取它的可能性就比較大。再進一步說,如果所選取的n種設(shè)備的帶寬的最小值b已經(jīng)確定,那么對于某種設(shè)備,我們就可以在那些生產(chǎn)這種設(shè)備的,帶寬大于等于b的制造商中進行選擇。當然是選那個價格最低的設(shè)備,因為答案的分子已經(jīng)確定為b,所以分母越小越好。看來只要枚舉b,再對于每個設(shè)備貪心的選擇最小價格就可以了,時間復(fù)雜度為OmnB),B為帶寬枚舉的數(shù)量。但問題又來了,應(yīng)該怎么枚舉帶寬,題目中并未給出帶寬的取值范圍,如果從0..maxB一個一個枚舉的話,既費時又會造成過多重復(fù)情況(如果枚舉那些在輸入中出現(xiàn)的兩個連續(xù)帶寬之間的值,最后的答案是一樣的)。所以我們應(yīng)該采取某個方法記錄輸入中出現(xiàn)過的帶寬(STL中的set是個不錯的選擇),再枚舉這些帶寬。在枚舉中,可能出現(xiàn)這種情況:枚舉b,選擇了n種設(shè)備,但選擇的所有設(shè)備的帶寬都大于b,那么最終用b/price就不是這種情況的正確答案。其實不用擔(dān)心,因為正確答案一定大于b/price。假設(shè)上面這種情況的實際帶寬最小值是b’,那個當我們再去枚舉b’時,至少有一個設(shè)備的帶寬等于b’,這次得到的答案也就是上面那種情況的答案,所以最終還是能得到正確解。

             

            代碼:

            #include <iostream>

            #include <map>

            #include <set>

            #include <climits>

            using namespace std;

             

            const int MAX = 105;

             

            struct Info

            {

                            int band, price;

            };

             

            struct Device

            {

                            int manuNum;

                            Info info[MAX];

                            map<int, int> minPrice;                 //map[i] = j 表示帶寬>=i的最小價格是j

                            int minBand, maxBand;

            };

             

            Device device[MAX];

            int deviceNum;

            set<int> band;                                                                  //輸入中出現(xiàn)過的band

            set<int>::iterator start, end;

            int maxBand, minBand;                                 //需要枚舉的band的最值

             

            int cmp( const void *a , const void *b )

            {

                            Info *c = (Info *)a;

                            Info *d = (Info *)b;

                            if(c->band != d->band)

                                            return d->band - c->band;

                            else

                                            return c->price - d->price;

            }

             

            void Input ()

            {

                            int i, j, max, min;

                            band.clear();

                            cin>>deviceNum;

                            for (i=0; i<deviceNum; i++)

                            {

                                            device[i].minBand = INT_MAX;

                                            device[i].maxBand = -1;

                                            cin>>device[i].manuNum;

                                            for (j=0; j<device[i].manuNum; j++)

                                            {

                                                            cin>>device[i].info[j].band>>device[i].info[j].price;

                                                            band.insert(device[i].info[j].band);

                                                            if ( device[i].info[j].band > device[i].maxBand )

                                                                            device[i].maxBand = device[i].info[j].band;

                                                            if ( device[i].info[j].band < device[i].minBand )

                                                                            device[i].minBand = device[i].info[j].band;

                                            }

                                                                           

                            }

            }

             

            void Pre ()                                           //預(yù)處理

            {

                            int i, j, min, b;

                            //計算所需枚舉的帶寬的最值

                            maxBand = INT_MAX;                   //maxBand為所有設(shè)備帶寬最大值的最小值

                            minBand = INT_MAX;                    //minBand為所有設(shè)備帶寬最小值的最小值

                            for (i=0; i<deviceNum; i++)

                            {

                                            if ( device[i].maxBand < maxBand )

                                                            maxBand = device[i].maxBand;

                                            if ( device[i].minBand < minBand )

                                                            minBand = device[i].minBand;

                            }

             

                            //對于每個設(shè)備,找到帶寬大于等于某一值的最小價格

                            for (i=0; i<deviceNum; i++)

                            {

                                            //band從大到小,band相等時price從小到大

                                            qsort(device[i].info, device[i].manuNum, sizeof(Info), cmp);

                                            device[i].minPrice.clear();

                                            min = device[i].info[0].price;

                                            b = device[i].info[0].band;

                                            device[i].minPrice[b] = min;

                                            for (j=1; j<device[i].manuNum; j++)

                                            {

                                                            if ( device[i].info[j].band == b )

                                                                            continue;

                                                            if ( device[i].info[j].price < min )

                                                            {

                                                                            min = device[i].info[j].price;

                                                            }

                                                            b = device[i].info[j].band;

                                                            device[i].minPrice[b] = min;

                                            }

                            }             

            }

             

            void Solve ()

            {

                            Pre();

             

                            int b, i, totalPrice;

                            double rate, ans;

                            map<int, int>::iterator it;

                            ans = 0;

                            start = band.find(minBand);

                            end = band.find(maxBand);

                            end ++;

                            while ( start != end )

                            {

                                            b = *start;

                                            start ++;

                                            totalPrice = 0;

                                            for (i=0; i<deviceNum; i++)

                                            {

                                                            //找到帶寬大于等于b的最小價格

                                                            for (it=device[i].minPrice.begin(); it!=device[i].minPrice.end(); it++)

                                                            {

                                                                            if ( it->first >= b )

                                                                            {

                                                                                            totalPrice += it->second;

                                                                                            break;

                                                                            }

                                                            }

             

                                            }

                                            rate = double(b) / totalPrice;

                                            if ( rate > ans )

                                                            ans = rate;

                            }

             

                            printf("%.3f\n", ans);

            }

             

            int main ()

            {

                            int test;

                            cin>>test;

                            while ( test -- )

                            {

                                            Input ();

                                            Solve ();

                            }

             

                            return 0;

            }

            posted on 2008-04-25 21:25 quxiao 閱讀(1524) 評論(6)  編輯 收藏 引用 所屬分類: ACM

            評論

            # re: PKU 1018 Communication System 2008-09-02 23:21 c迷2
            寫得太好了,我把它轉(zhuǎn)到我的空間里面啦,你不會介意吧?  回復(fù)  更多評論
              

            # re: PKU 1018 Communication System 2008-09-03 19:30 ACM-Boy
            @c迷2
            不介意,這里就是一個供大家一起思考、討論的平臺,幫助了他人,也提高了自己。  回復(fù)  更多評論
              

            # re: PKU 1018 Communication System 2009-01-18 10:50 zyq
            這個程序?qū)懙牧_里羅嗦的!  回復(fù)  更多評論
              

            # re: PKU 1018 Communication System 2009-03-13 15:51 CaBreak
            寫的好,支持!  回復(fù)  更多評論
              

            # re: PKU 1018 Communication System 2009-04-13 12:39 liuwuyue
            受教了 呵呵 謝謝   回復(fù)  更多評論
              

            # re: PKU 1018 Communication System 2009-07-01 16:27 chhaya
            這么長~~~  回復(fù)  更多評論
              

            久久久久中文字幕| 久久本道久久综合伊人| 久久婷婷是五月综合色狠狠| 日韩欧美亚洲综合久久影院Ds | 成人综合伊人五月婷久久| 久久精品中文无码资源站| 99久久中文字幕| 久久精品国产男包| 久久精品人人做人人爽电影蜜月 | 中文字幕乱码久久午夜| 久久国产精品无码HDAV | 久久精品国产亚洲沈樵| 久久久WWW成人| 久久ww精品w免费人成| 中文字幕久久亚洲一区| 久久精品这里热有精品| 久久精品国产欧美日韩99热| 亚洲乱亚洲乱淫久久| 97久久婷婷五月综合色d啪蜜芽| 久久免费线看线看| 色综合久久中文字幕无码| 欧美激情精品久久久久久久九九九| 久久综合精品国产二区无码| 久久中文字幕精品| 久久久久99精品成人片三人毛片 | 亚洲AV无码1区2区久久| 久久AAAA片一区二区| 免费观看久久精彩视频| 蜜臀久久99精品久久久久久小说 | 久久久久久久精品妇女99| 久久最近最新中文字幕大全 | 麻豆成人久久精品二区三区免费 | 久久久久久亚洲精品不卡| 久久综合中文字幕| 久久精品国产99国产电影网 | AV无码久久久久不卡网站下载| 四虎影视久久久免费观看| 久久久久久久久久免免费精品 | 久久久精品日本一区二区三区| 久久久久久久99精品免费观看| 国产精品免费福利久久|