首页 > 专题系列 > Java解POJ > POJ 1018 Communication System [解题报告] Java
2013
11-08

POJ 1018 Communication System [解题报告] Java

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;
 import java.io.InputStreamReader;

 public class Main {

     double bp = 0;

     public Main() throws NumberFormatException, IOException {
         BufferedReader read = new BufferedReader(new InputStreamReader(
                 System.in));
         int t = Integer.parseInt(read.readLine());
         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++) {
             num = Integer.parseInt(read.readLine());
             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++) {
                 s = read.readLine().split(" ");
                 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();}.

  4. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。