2013
11-08

# Communication System

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.

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 manufacturers for the i-th device, followed by mi pairs of positive integers in the same line, each indicating the bandwidth and the price of the device respectively, corresponding to a manufacturer.

Your program should produce a single line for each test case containing a single number which is the maximum possible B/P for the test case. Round the numbers in the output to 3 digits after decimal point.

1 3
3 100 25 150 35 80 25
2 120 80 155 40
2 100 100 120 110

0.649

import java.io.BufferedReader;
import java.io.IOException;

public class Main {

double bp = 0;

public Main() throws NumberFormatException, IOException {
System.in));
int num;
int[][] b;
int[][] p;
int[] n;
int bmin = Integer.MAX_VALUE;
int[] bmaxs;
int bmax;
String[] s;
int sum;
int temp;
for (int i = 0; i < t; i++) {
b = new int[num][];
p = new int[num][];
n = new int[num];
bmin = Integer.MAX_VALUE;
bmaxs = new int[num];
bmax = Integer.MAX_VALUE;
for (int j = 0; j < num; j++) {
n[j] = Integer.parseInt(s[0]);
b[j] = new int[n[j]];
p[j] = new int[n[j]];
for (int k = 0; k < n[j]; k++) {
b[j][k] = Integer.parseInt(s[k * 2 + 1]);
if (b[j][k] > bmaxs[j]) {
bmaxs[j] = b[j][k];
}
if (b[j][k] < bmin) {
bmin = b[j][k];
}
p[j][k] = Integer.parseInt(s[k * 2 + 2]);
}
}
for (int j = 0; j < num; j++) {
if (bmaxs[j] < bmax) {
bmax = bmaxs[j];
}
}
bp = 0;
for (int j = bmin; j <= bmax; j++) {
sum = 0;
for (int k = 0; k < num; k++) {
temp = Integer.MAX_VALUE;
for (int h = 0; h < n[k]; h++) {
if (b[k][h] >= j && p[k][h] < temp) {
temp = p[k][h];
}
}
sum += temp;
}
if ((double) j / sum > bp) {
bp = (double) j / sum;
}
}
System.out.printf("%.3f\n", bp);
}
}

public static void main(String[] args) throws NumberFormatException,
IOException {
new Main();
}
}

1. 我没看懂题目
2
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5
我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
第二个是7 0 6 -1 1 -6 7输出是14 7 7
不知道题目例子是怎么得出来的

2. Often We don’t set up on weblogs, but I would like to condition that this established up really forced me individually to do this! considerably outstanding publish

3. 嗯 分析得很到位，确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样：push时，比较要push的elem和辅助栈的栈顶，elem<=min.top()，则min.push(elem).否则只要push（elem）就好。在pop的时候，比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();}，否则{stack.pop();}.