北大ACM(POJ1018-Communication System)

发布时间:2017-3-8 8:24:45编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"北大ACM(POJ1018-Communication System) ",主要涉及到北大ACM(POJ1018-Communication System) 方面的内容,对于北大ACM(POJ1018-Communication System) 感兴趣的同学可以参考一下。

Question:http://poj.org/problem?id=1018
问题点:枚举。
 1 Memory: 564K        Time: 329MS
 2 Language: C++        Result: Accepted
 3 
 4 #include <iostream>
 5 #include <iomanip>
 6 using namespace std;
 7 
 8 struct BP
 9 {
10     int i;//第i种设备
11     int B;//设备带宽
12     int P;//设备价格
13 };
14 int cmp1(const void* a,const void* b)//排序按 i,P 升序排列
15 {
16     BP* ca = (BP*)a;
17     BP* cb = (BP*)b;
18     return (ca->i==cb->i?(ca->P - cb->P):(ca->i - cb->i));
19 }
20 int cmp2(const void* a,const void* b)//排序按 B 升序排列
21 {
22     BP* ca = (BP*)a;
23     BP* cb = (BP*)b;
24     return ca->B - cb->B;
25 }
26 int main()
27 {
28     int eg,num;
29     cin>>eg;
30     BP bp[10000];//排序按 i,P 升序排列
31     BP orderB[10000];//排序按 B 升序排列
32     double maxBP;//结果
33     int same,maxB,temp,i,j,k,cnt,idx;
34     while(eg--)
35     {
36         cin>>num;
37         memset(bp,0,sizeof(bp));
38         k = cnt = maxB = 0;
39         maxBP = 0;
40         for(i=0;i<num;i++)
41         {
42             cin>>same;//一种设备的数量
43             cnt += same;//所有设备的数量
44             temp = 0;//记录一种设备的最大带宽
45             for(j=0;j<same;j++,k++)
46             {
47                 bp[k].i = i;
48                 cin>>bp[k].B>>bp[k].P;
49                 temp = (temp>0 && temp>bp[k].B)?temp:bp[k].B;
50             }
51             maxB = (maxB>0 && maxB<temp)?maxB:temp;//取所有设备最大带宽的的最小值,即B的取值上限
52         }
53         memcpy(orderB,bp,sizeof(bp));
54         qsort(bp,cnt,sizeof(BP),cmp1);//排序按 i,P 升序排列,用于取各类设备中大于B的最小P
55         qsort(orderB,cnt,sizeof(BP),cmp2);//排序按 B 升序排列 ,用于枚举B
56         for(i=0;i<cnt && orderB[i].B<=maxB;i++)
57         {
58             k = orderB[i].B;//枚举B
59             temp = orderB[i].P;//当前情况 最小P
60             for(j=0,idx=0;j<cnt && idx < num;j++)
61             {
62                 if(bp[j].i == orderB[i].i || bp[j].B < k || idx > bp[j].i) continue;
63                 temp += bp[j].P;
64                 idx = bp[j].i+1;//如果第j类设备已取,idx指向下一类设备,(不能使用 idx++)
65             }
66             maxBP = (maxBP > 0 && maxBP > double(k)/temp?maxBP:double(k)/temp);//取最大B/P值
67         }
68         cout<<fixed<<setprecision(3)<<maxBP<<endl;//输出必须小数点后3位,如1要输出1.000
69     }
70     //system("pause");
71     return 0;
72 }


上一篇:java学习笔记-2
下一篇:线程调度的问题:Lock Convoy(锁封护)与Priority Inversion(优先级反转)

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款