编程题目求解7

来源：百度知道 编辑：UC知道 时间：2024/06/06 00:07:14
Description

We have received an order from Pizoor Communications Inc. for a special communication system. The system consists of several devices. For each device, we are free to choose from several manufacturers. Same devices from two manufacturers differ in their maximum bandwidths and prices.
By overall bandwidth (B) we mean the minimum of the bandwidths of the chosen devices in the communication system and the total price (P) is the sum of the prices of all chosen devices. Our goal is to choose a manufacturer for each device to maximize B/P.

Input

The first line of the input file contains a single integer t (1 ≤ t ≤ 10), the number of test cases, followed by the input data for each test case. Each test case starts with a line containing a single integer n (1 ≤ n ≤ 100), the number of devices in the communication system, followed by n lines in the following format: the i-th line (1 ≤ i ≤ n) starts with mi (1 ≤ mi ≤ 100), the number of manufactur

#include <iostream>
#include <map>
#include <set>
#include <climits>
using namespace std;

const int MAX = 105;

struct Info
{
int band, price;
};

struct Device
{
int manuNum;
Info info[MAX];
map<int, int> minPrice; //map[i] = j 表示带宽>=i的最小价格是j
int minBand, maxBand;
};

Device device[MAX];
int deviceNum;
set<int> band; //输入中出现过的band
set<int>::iterator start, end;
int maxBand, minBand; //需要枚举的band的最值

int cmp( const void *a , const void *b )
{
Info *c = (Info *)a;
Info *d = (Info *)b;
if(c->band != d->band)
return d->