poj1018 Communication System —

poj1018 Communication System ——贪心+枚举

题目大意：

　　有n种设备，每种设备有mi个选择，每种设备选择一个，每个设备都有一个带宽值和价钱，要求每种设备选择一个，最终选择的n个设备里面，带宽B是这n个设备里面所有带宽的最小值吗，价钱P为这n个设备价钱的和，求B/P的最大值。

题目思路：

　　这题开始没读懂题意，后来搜的题意之后才明白。然后没有思路……看了人家的思路，貌似懂了……然后就开始写，写跪了……开始的方法是，求出所有这n种设备里面每种设备的带宽的最小值，依次枚举这些最小值就可以了。总是WA……

　　昨天纠结一晚上，今天早上又想了一下，发现原来的想法是有问题的，应该一直枚举到所有n中设备里面每种带宽的最大值的最小值。第一：保证这n种设备每一种都可以选上。第二：虽然枚举的B值比原来大了，所得到的的价钱不小于我原来的做法所得到的的价钱，但是，重点来了：B也增大了啊！有木有！所以，这就是我当初没有想到的！

 1 #include <iostream>
 2 #include <cstdlib>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <algorithm>
 6 using namespace std;
 7 #define MAXN 0x7fffffff
 8 #define MINN -MAXN
 9 const int MAX = 100+10;
10 typedef struct node {
11   int p, b, cnt;
12   bool operator < (const node & other ) const {
13     if (p != other.p) return p < other.p;
14     else return b < other.b;
15   }
16 }node;
17 typedef struct sys {
18   node de[MAX];
19   int Min, Max, cnt;
20   bool operator < (const sys &other) const {
21     return Min < other.Min;
22   }
23 }sys;
24 sys ban[MAX];
25 void solve() {
26   int n; scanf("%d", &n);
27   int i, j, tMin, tMax, sump, k;
28   double ans;
29   for (i = 0; i < n; ++i) {
30     scanf("%d", &ban[i].cnt);
31     tMin = MAXN; tMax = MINN;
32     for (j = 0; j < ban[i].cnt; ++j) {
33       scanf("%d%d", &ban[i].de[j].b, &ban[i].de[j].p);
34       if (tMin > ban[i].de[j].b) tMin = ban[i].de[j].b;
35       if (tMax < ban[i].de[j].b) tMax = ban[i].de[j].b;
36     }
37     ban[i].Min = tMin; ban[i].Max = tMax;
38     sort(ban[i].de, ban[i].de + ban[i].cnt);
39   }
40   sort(ban, ban+n);
41   int start, end; start = ban[0].Min; end = MAXN;
42   for (i = 0; i < n; ++i) {
43     if (end > ban[i].Max) end = ban[i].Max;
44   }
45   ans = MINN;
46   for (i = start; i <= end; ++i) {
47     sump = 0;
48     for (j = 0; j < n; ++j) {
49       k = 0;
50       while (ban[j].de[k].b < i) ++k;
51       sump += ban[j].de[k].p;
52     }
53     double re = (double)i/(double)sump;
54     if (re > ans) ans = re;
55   }
56   /*
57   for (i = 0; i < n; ++i) {
58     sump = 0;
59     int tmp = ban[i].Min; 
60     bool mrk = true;
61     for (k = 0; k < n; ++k) {
62       if (ban[k].Max < tmp) {mrk = false; break;}
63       j = 0;
64       while (ban[k].de[j].b < tmp) j++;
65       sump += ban[k].de[j].p;
66     }
67     if (!mrk) continue;
68     double re = (double)tmp/(double)sump;
69     //cout << "tmp = " << tmp << endl;
70     //cout << "sump = " << sump << endl;
71     if (re > ans) ans = re;
72   }
73   */
74   printf("%.3f\n", ans);
75 }
76 void init() {
77   //freopen("1018.in", "r", stdin);
78   int t; scanf("%d", &t);
79   while (t--) {
80     solve();
81   }
82 }
83 int main(void) {
84   init();
85   return 0;
86 }

调试的时候的注释就不删了……都是血淋淋的教训

好吧，我的做法是有多繁琐……人家的代码都超短o(╯□╰)o