这个题目一开始不知道如何下手,感觉很像背包,里面有两个变量,一个带宽B,一个价格P,有n个设备,每个设备有k个可选的器材(只需选一个),每个器材都有自己的B和P,
n个设备选n个器材,最终,FB=所有器材里最小的B,FP=总的价格,要使得FB/FP最大
这种题目得先把一个变量给控制起来,或者说枚举其中一个变量之后,再通过dp的方法得到另一个变量的最优值,千万别想一步登天
像这个题目,我们如果先把每个设备对应的器材按价格升序排序,然后我枚举可能的FB,对于每个设备,我从前往后扫,一旦扫到了B>=FB(合法数据),就停止,取该值,最后扫完整个n个设备,得到的值必定是我枚举 的FB对应的最大FB/FP,这个显而易见嘛。。因为数据量不大,所以可以用。当然我算了下峰值的复杂度可以达到10的8次方,但是其实达不到,其中很难每个循环都运行完。
其实这样看来倒不像DP了,其实是暴力枚举了
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
struct node
{
int b,v;
bool operator < (const node&rhs) const{
return v<rhs.v;
}
};
vector<node>G[110];
int B[10010];
int n,cnt;
int main()
{
int t;
scanf("%d",&t);
while (t--)
{
cnt=0;
scanf("%d",&n);
for (int i=0;i<=n;i++) G[i].clear();
for (int i=1;i<=n;i++){
int k,a,b;
scanf("%d",&k);
while (k--){
scanf("%d%d",&a,&b);
B[cnt++]=a;
G[i].push_back((node){a,b});
}
sort(G[i].begin(),G[i].end());
}
sort(B,B+cnt);
int m=0;
for (int i=1;i<cnt;i++){
if (B[i]!=B[i-1]) B[++m]=B[i];
}
double ans=0.0;
for (int i=0;i<=m;i++){
bool flag=1;
double sum=0;
for (int j=1;j<=n && flag;j++){
int r=G[j].size();
for (int k=0;k<r;k++){
if (G[j][k].b>=B[i]){
sum+=(double)G[j][k].v;
break;
}
if (k==r-1 && G[j][k].b<B[i])flag=0;
}
}
if (!flag) continue;
ans=max(ans,(double)B[i]*1.0/sum);
}
printf("%.3f\n",ans);
}
return 0;
}