poj1018

2019-11-11 02:57:29

字体：大中小

来源：转载

供稿：网友

题目大意：

一套系统需要几个设备，每个设备有几个不同的制造商。不同的制造商在最大带宽和价格方面不同。整个系统的带宽我们指选择的设备的最小带宽，价格是总和。我们的目标是选择设备使得B/P最大

解题思路：

贪心算法+遍历

代码如下：

#include<stdio.h>#include<string.h>int main(){ int i,j,k,m,min,max,high,low,t,sum; int b[101][101],p[101][101],num[101],flag[32767]; double b_p,mmax; scanf("%d",&t); while(t--) { memset(flag,0,sizeof(flag)); high=32767; low=32767; scanf("%d",&m); for(i=0;i<m;i++) { min=10000; max=1; scanf("%d",&num[i]); for(j=0;j<num[i];j++) { scanf("%d",&b[i][j]); scanf("%d",&p[i][j]); flag[b[i][j]]=1; if(max<b[i][j]) max=b[i][j]; if(min>b[i][j]) min=b[i][j]; } if(low>min) low=min; if(high>max) high=max; } mmax=0; for(i=low;i<=high;i++) { if(flag[i]) { sum=0; for(j=0;j<m;j++) { min=32767; for(k=0;k<num[j];k++) { if(i <=b[j][k]) { if(min>p[j][k]) min=p[j][k]; } } sum+=min; } b_p=(double)i/(double)sum; if(mmax<b_p) mmax=b_p; } } PRintf("%.3lf/n",mmax); } return 0;}

上一篇：Xgboost | 在Win10中安装

下一篇：关于500 Internal Server Error的问题解决