首页 > 专题系列 > Java解POJ > POJ 2442 Sequence [解题报告] Java
2013
11-11

POJ 2442 Sequence [解题报告] Java

Sequence

问题描述 :

Given m sequences, each contains n non-negative integer. Now we may select one number from each sequence to form a sequence with m integers. It’s clear that we may get n ^ m this kind of sequences. Then we can calculate the sum of numbers in each sequence, and get n ^ m values. What we need is the smallest n sums. Could you help us?

输入:

The first line is an integer T, which shows the number of test cases, and then T test cases follow. The first line of each case contains two integers m, n (0 < m <= 100, 0 < n <= 2000). The following m lines indicate the m sequence respectively. No integer in the sequence is greater than 10000.

输出:

For each test case, print a line with the smallest n sums in increasing order, which is separated by a space.

样例输入:

1
2 3
1 2 3
2 2 3

样例输出:

3 3 4

解题代码:

import java.util.Scanner;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Comparator;

public class Main{
         private int[] array1;
         private int[] array2;
         PriorityQueue< Integer> heap;

       public Main(){
        }

       private void go(){
         Scanner in=new Scanner(System.in);
        int t=in.nextInt();
        while(t-->0){
         int m=in.nextInt();
         int n=in.nextInt();
         array1=new int[n];
         array2=new int[n];
         heap=new PriorityQueue< Integer>(n,new Comparator< Integer>(){
               @Override
               public int compare(Integer o1, Integer o2) {
                  if(o1< o2)
                   return 1 ;
                  else if(o1>o2){
                   return -1;
                 }else{
                   return 0;
                 }
               }     
         });
          for(int i=0;i< n;i++)  
            array1[i]=in.nextInt();  
         Arrays.sort(array1); 
         for(int i=1;i< m;i++){  
           
            for(int j=0;j< n;j++){  
              array2[j]=in.nextInt();  
              heap.offer(array1[0]+array2[j]);
              
            }  
            Arrays.sort(array2);  
            
            for(int k=1;k< n;k++)  
             for(int l=0;l< n;l++){  
                if(array1[k]+array2[l]>heap.peek())  
                    break;  
                heap.poll();  
                heap.offer(array1[k]+array2[l]);  
            }  
            for(int k=n-1;k>=0;k--)  
            {  
                array1[k]=heap.poll();  
               
            }  
        }  
      
        System.out.printf("%d",array1[0]);  
        for(int i=1;i< n;i++)  
         System.out.printf(" %d",array1[i]);  
        System.out.println();  
      } 
  } 


   public static void main(String[] args){
     Main ma=new Main();
      ma.go();
   }
}

  1. 你的理解应该是:即使主持人拿走一个箱子对结果没有影响。这样想,主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率,但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3