yoyouhappy的秘密花园
欢迎来到我的秘密花园^^
posts - 16,comments - 33,trackbacks - 0

题目大意:
产品有n个部分 组成  每个部分有m种选择,每个部件 有bandwith和price两种属性 
求 一种选择方案使B/P 最大   其中 B是各个部件bandwith的最小值  P是各个部件price的和
我的做法:
将bandwith排序,然后分别以每一个bandwith最为最小值时 求出可取方案中price值最小的 那个(即 使B/P最大)
然后综合起来  求最大的B/P

下面是我的代码:


虽然AC了,但是还是有一点疑惑,在某一minBand为最小值时,所取得方案中肯定包含一个产品选择的bandwith = minBand,否则最小值不是minBand,但是我没有做这个判断


代码如下,仅作参考:

 1#include <iostream>
 2#include <set>
 3#include <algorithm>
 4using namespace std;
 5
 6struct Device
 7{
 8    int nChoice;
 9    int quality[102][2];
10};
11
12int main()
13{
14    int ncase;
15    cin >> ncase;
16    while ( ncase-- ){
17
18        int n;
19        double ratio = 0;
20        set <int> intSet;
21        set <int>::iterator sp;
22        cin >> n;
23        Device *s = new Device[n];
24        
25        for( int i = 0; i < n; i++ ) {
26            cin >> s[i].nChoice;
27            for( int j = 0; j < s[i].nChoice; j++ ){
28                cin >> s[i].quality[j][0] >> s[i].quality[j][1];
29                intSet.insert( s[i].quality[j][0] );
30            }
31        } 
32        
33        for( sp = intSet.begin(); sp != intSet.end(); sp++ ){
34            int totalPrice = 0;
35            int minBand = *sp;
36            for( int i = 0; i < n; i++){//选每一种产品
37                int min = 100000;
38                for( int j = 0; j < s[i].nChoice; j++ ){
39                    if( s[i].quality[j][0] >= minBand && min > s[i].quality[j][1] )
40                        min = s[i].quality[j][1];
41                }
42                totalPrice += min;               
43            } 
44            if( ratio < (double) (minBand) / (double) totalPrice ){
45                ratio = (double) (minBand) / (double) totalPrice;            
46            }
47        }
48         printf( "%.3lf\n", ratio );
49
50        delete s;
51    }
52    system("pause");
53    return 0;
54}
55

一开始,我写的是min = s[i].quality[0][1];弄了好久都不知道哪里错了,后来发现原来第一个不一定取,这个做每次都toalPrice都是一样的....标出来,警示自己一下,呵呵 估计 大家都没有错的这么白痴的 >_<
posted on 2008-01-28 16:11 yoyouhappy 阅读(2093) 评论(1)  编辑 收藏 引用 所属分类: yoyo的解题报告

FeedBack:
# re: POJ 1018 Communication System
2008-10-24 10:55 | infinity
我觉得你的做法有问题.  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


Priceline Travel
Priceline Travel