POJ 1018 Communication System(枚举)

本文主要是介绍POJ 1018 Communication System(枚举)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

http://poj.org/problem?id=1018

题解：

我们可以枚举每一种B可能的值，然后寻找每一行里大于等于B里最小的P。

代码：

#include<cstdio>
#include<stdlib.h>
struct in
{double B,P;
}a[101][101];
double b[10001];
int t[101];
int cmp(const void *a,const void *b)
{in *c=(in*)a;in *d=(in*)b;if(c->P>d->P) return 1;else return -1;
}
double max(double a,double b)
{return a>b?a:b;
}
int main()
{int T;scanf("%d",&T);while(T--){int n;scanf("%d",&n);int i,j;int size=0;for(i=0;i<n;i++){scanf("%d",&t[i]);for(j=0;j<t[i];j++){scanf("%lf%lf",&a[i][j].B,&a[i][j].P);b[size++]=a[i][j].B;}qsort(a[i],t[i],sizeof(a[0][0]),cmp);}int si;double ans=0;double Psum=0;for(si=0;si<size;si++){for(i=0;i<n;i++){for(j=0;j<t[i];j++){if(a[i][j].B>=b[si]){Psum+=a[i][j].P;break;}}if(j==t[i]){Psum=0;break;}}if(Psum!=0){ans=max(ans,b[si]/Psum);}Psum=0;}printf("%.3lf\n",ans);}return 0;
}

这篇关于POJ 1018 Communication System(枚举)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---