这题是2002年德黑兰，第一届伊朗全国互联网编程竞赛

看着好像很高大上的样子，然鹅这道题并不难。先大致分析下题意

描述

我们收到了皮佐尔通讯公司的一份特殊的通信系统订单。系统由很多设备组成。对于每种设备，我们都可以从多家制造商中*选择一个。任意两家制造商所生产的同一设备的最大带宽或价格不同。
总带宽（B）指通信系统中所有所选的设备中的最小带宽，总价格（P）是所有所选设备的价格之和。我们的目标是为每种设备选择制造商以最大化性价比，即B/P。

输入

输入文件的第一行包含一个整数t（1≤t≤10），测试数据数量，之后有t个测试数据的输入数据。每个测试数据均以一个整数n（1≤n≤100）（通信系统中的设备数量）的单独一行开头，后接以下格式的n行：第i行（1≤i≤n）中，第一个整数表示第i个设备的制造商数量m[i]（1≤m[i]≤100），然后是m[i]对正整数对，每对分别表示这个制造商所生产的设备的最大带宽和价格。

输出

输出应包含t行（即每个测试数据各一行），每行一个数字，表示该测试数据可能的最大B/P。将输出的数字四舍五入到小数点后3位。

 

(好吧，题目bb了这么多，简单来说意思就是，给每个设备选择一个制造商，使得所选择的最大)(不会用博客园的公式编辑器)

 

这道题很显然，暴力+贪心可以做。（思路在代码的注释中）时间复杂度约为O(n⁴)

代码如下:

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 using namespace std;
 5 int t,n,m[101],b[101][101],p[101][101],tot;
 6 double ans=100000;
 7 int solve(int a) {
 8     int inbptot=0;
 9     for(int i=1; i<=n; i++) {
10         minp=100000;
11         for(int j=1; j<=m[i]; j++)
12             if((b[i][j]>=a)&&(p[i][j]<minp)) {//寻找符合条件的最小p
13             // 当前带宽>所枚举带宽(a)&& 当前价格<此前最小价格
14                 minp=p[i][j];
15             }
16         tot+=minp;//累计价格
17     }
18     return tot;
19 }
20 //暴力解法
21 int main() {
22     cin>>t;//共t组测资 
23     while(t--) {
24         ans=0;
25         cin>>n;
26         for(int i=1; i<=n; i++) {
27             cin>>m[i];
28             for(int j=1; j<=m[i]; j++) {
29                 cin>>b[i][j]>>p[i][j];
30             }
31         }//第30-36行按要求读入 
32         for(int i=1; i<=n; i++) {
33             for(int j=1; j<=m[i]; j++) {//寻找每个设备 
34                 int minb=b[i][j],tot=solve(minb);//枚举b(带宽); 
35                 if(ans<minb*1.0/tot){//    性价比>原性价比 (b/p>ans)
36                     ans=minb*1.0/tot;
37                 }
38             }
39         }
40         printf("%.3lf\n",ans);//按要求输出 
41     }
42     return 0;
43 }

 

这个代码跑完，391ms，看着特别不爽，于是乎，

冥思苦想......

冥思苦想......

想出了个稍微优化的算法，依旧是贪心+暴力

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 using namespace std;
 5 int t,n,m[101],b[101][101],p[101][101],tot,high,low,flag[32777];
 6 double ans=100000;
 7 int solve(int a) {
 8     int minp,tot=0;
 9     for(int i=1; i<=n; i++) {
10         minp=100000;
11         for(int j=1; j<=m[i]; j++)
12             if((b[i][j]>=a)&&(p[i][j]<minp)) {//寻找符合条件的最小p
13                 // 当前带宽>所枚举带宽(a)&& 当前价格<此前最小价格
14                 minp=p[i][j];
15             }
16         tot+=minp;//累计价格
17     }
18     return tot;
19 }
20 int main() {
21     cin>>t;//共t组测资
22     while(t--) {
23         ans=0;
24         cin>>n;
25         memset(flag,0,sizeof(flag));
26         high=0;
27         low=32767;
28         for(int i=1; i<=n; i++) {
29             cin>>m[i];
30             for(int j=1; j<=m[i]; j++) {
31                 cin>>b[i][j]>>p[i][j];
32                 if(high<b[i][j])//更新数据最小值
33                     high=b[i][j];
34                 if(low>b[i][j])//更新数据最大值
35                     low=b[i][j];
36                 flag[b[i][j]]=1;
37             }
38         }//第30-36行按要求读入
39         for(int i=low; i<=high; i++)
40             if(flag[i]) {
41                 int minb=i,tot=solve(minb);//枚举b(带宽);
42                 if(ans<minb*1.0/tot) { //    性价比>原性价比 (b/p>ans)
43                     ans=minb*1.0/tot;
44                 }
45             }
46     printf("%.3lf\n",ans);//按要求输出
47     }
48     return 0;
49 }

跑完30ms舒服多了.