首页 > 专题系列 > Java解POJ > POJ 1065 Wooden Sticks [解题报告] Java
2013
11-09

POJ 1065 Wooden Sticks [解题报告] Java

Wooden Sticks

问题描述 :

There is a pile of n wooden sticks. The length and weight of each stick are known in advance. The sticks are to be processed by a woodworking machine in one by one fashion. It needs some time, called setup time, for the machine to prepare processing a stick. The setup times are associated with cleaning operations and changing tools and shapes in the machine. The setup times of the woodworking machine are given as follows:

(a) The setup time for the first wooden stick is 1 minute.

(b) Right after processing a stick of length l and weight w , the machine will need no setup time for a stick of length l’ and weight w’ if l <= l' and w <= w'. Otherwise, it will need 1 minute for setup.

You are to find the minimum setup time to process a given pile of n wooden sticks. For example, if you have five sticks whose pairs of length and weight are ( 9 , 4 ) , ( 2 , 5 ) , ( 1 , 2 ) , ( 5 , 3 ) , and ( 4 , 1 ) , then the minimum setup time should be 2 minutes since there is a sequence of pairs ( 4 , 1 ) , ( 5 , 3 ) , ( 9 , 4 ) , ( 1 , 2 ) , ( 2 , 5 ) .

输入:

The input consists of T test cases. The number of test cases (T) is given in the first line of the input file. Each test case consists of two lines: The first line has an integer n , 1 <= n <= 5000 , that represents the number of wooden sticks in the test case, and the second line contains 2n positive integers l1 , w1 , l2 , w2 ,..., ln , wn , each of magnitude at most 10000 , where li and wi are the length and weight of the i th wooden stick, respectively. The 2n integers are delimited by one or more spaces.

输出:

The output should contain the minimum setup time in minutes, one per line.

样例输入:

3 
5 
4 9 5 2 2 1 3 5 1 4 
3 
2 2 1 1 2 2 
3 
1 3 2 2 3 1 

样例输出:

2
1
3

解题代码:

import java.util.*;   
    
public class Main{   
    public static void main(String[] args){   
        int l[]=new int[10000];   
        int w[]=new int[10000];   
        int tt[]=new int[5000];   
        int k=0;   
        Scanner keyin=new Scanner(System.in);   
        int m=keyin.nextInt();   
        int mm=m;   
        int n=0;   
        for(;m>0;m--){   
            n=keyin.nextInt();   
            for(int j=0;j< n;j++){   
                l[j]=keyin.nextInt();   
                w[j]=keyin.nextInt();   
            }   
  
            int time=0,c=0;   
            for(int t=0;t<=n-2;t++){   
                for(int s=n-2;s>=t;s--){   
                    if(l[s]>l[s+1]){   
                        int temp=l[s];   
                        l[s]=l[s+1];   
                        l[s+1]=temp;   
                        temp=w[s];   
                        w[s]=w[s+1];   
                        w[s+1]=temp;   
                    }   
                }   
            }   
  
            for(int p=0;p< n;p++){   
                if(w[p]!=-1){   
                    time++;   
                    c=w[p];   
                    for(int q=p+1;q< n;q++){   
                        if(w[q]>=c){   
                            c=w[q];   
                            w[q]=-1;   
                        }   
                    }   
                }   
            }   
            tt[k++]=time;   
        }   
        for(int r=0;r< mm;r++)   
            System.out.println(tt[r]);   
    }   
}

  1. int half(int *array,int len,int key)
    {
    int l=0,r=len;
    while(l<r)
    {
    int m=(l+r)>>1;
    if(key>array )l=m+1;
    else if(key<array )r=m;
    else return m;
    }
    return -1;
    }
    这种就能避免一些Bug
    l,m,r
    左边是l,m;右边就是m+1,r;