這題用的是貪心算法，不過在貪心之前還是要進行部分處理的。
首先就是題目要求B/P盡可能的大，所以P應該盡可能的小，B應該盡可能的大。但是B和P的處理方式是不一樣的，B是所有帶寬中最小的那一個，P是所有設備的總價錢，所以我能想到一個方法就是一個一個的枚舉B，本來我是不敢這樣想的，可是題目給的時間比較長，我覺得應該問題不大，當我運行之後，竟然只是0ms，讓我吃了一驚。然後再選擇設備，這時候就要用到貪心：
給定一個band，對於一個設備，在各個生產廠家之間的選擇，顯然帶寬要比band大，在這個中選擇價錢最便宜的。
我的具體處理細節如下：
1、對所有的band進行升序排序，枚舉的時候從最小的開始，當枚舉到一個band，某一個設備無法選出，也就是說該設備的各個生產廠家的帶寬都沒有band大，那麼就結束了。
2、對每個設備的band進行降序排序，這樣在查找最小的price的時候比較方便。
#include
#include
#include
#include
#include
#include
using namespace std;
const int inf=1<<28;
int band[10002],num[102];
struct Device
{
int band;
int price;
}device[102][102];
int n,m;
int solve(int t)
{
int t1=0,t2;
for(int i=1;i<=n;i++)
{
t2=inf;
for(int j=1;j<=num[i];j++)
{
if(device[i][j].banddevice[i][j].price)
t2=device[i][j].price;
}
if(t2==inf)
return -1;
t1+=t2;
}
return t1;
}
bool cmp(Device a,Device b)
{
return a.band>b.band;
}
int main()
{
int t;
scanf(%d,&t);
while(t--)
{www.2cto.com
scanf(%d,&n);
int top=1;
for(int i=1;i<=n;i++)
{
scanf(%d,&m);
num[i]=m;
for(int j=1;j<=m;j++)
{
scanf(%d%d,&device[i][j].band,&device[i][j].price);
band[top++]=device[i][j].band;
}
}
sort(band+1,band+top);
for(int i=1;i<=n;i++)
sort(device[i]+1,device[i]+num[i]+1,cmp);
int t_band=0,sum;
double ans=0.0;
for(int i=1;i
