首页 > 专题系列 > Java解POJ > POJ 2751 Saving Endeavour [解题报告] Java
2013
11-11

POJ 2751 Saving Endeavour [解题报告] Java

Saving Endeavour

问题描述 :

Space shuttle Endeavour (Endeavour is of British style, and Endeavor is of American style. Why NASA uses the British style? You can find the answer by Baidu or Google) is in danger!

Endeavour meets the same problem as Columbus had met in 2003. When it was sent into space, some material on the surface of the space shuttle is damaged. When it reenters the atmosphere, hot air may destroy the shuttle and make it fall into pieces. NASA says that the only method to save Endeavour is to send another shuttle into space to help repair the Endeavour. But considering the condition of other shuttles available, such as Atlantis and Discovery, scientists think they are not capable to complete the demanding task. NASA has to build another new space shuttle.

There are N parts of this new shuttle need to be built. Because the shuttle will be assembled before all parts are ready. NASA wants to minimize the time to build all parts.

There are two workshops S1 and S2. A part must be processed by these two workshops in order, which means that a part must be processed first in S1 and then in S2. It is known that a workshop cannot process more than one part simultaneously. You job is to calculate the minimum time to build all parts.

输入:

For every test block in the input, the first line contains an integer N (1 <= N <= 10000), representing the number of parts. Next follow N lines. Each line contains two integers a and b (0 <= a, b <= 100), representing the time consumed in S1, S2 for the corresponding part.

There is a single 0 after the last test block, and you should not process it.

输出:

There is only one line for one test block, namely the earliest finishing time.

样例输入:

4
1 2
3 4
5 6
7 8
4
10 1 
10 1 
1 10
1 10
5
4 5
4 1
30 4
6 30
2 3
6
5 7
1 2
8 2
5 4
3 7
4 4
0

样例输出:

24
23
47
28

解题代码:

/* @author: */
import java.util.Scanner;   
public class Main {   
   static int a[][]=new int[10001][2];
   static int b[][]=new int[10001][2];
   static int an,bn;

   static void sort(){
    int i,j,t1,t2;
    for(i=0;i< an;i++)
        for(j=0;j< an;j++)
        {
            if(a[i][0]< a[j][0])
            {
                t1=a[i][0];t2=a[i][1];
                a[i][0]=a[j][0];a[i][1]=a[j][1];
                a[j][0]=t1;a[j][1]=t2;   
            }    
        }    
    for(i=0;i< bn;i++)
        for(j=0;j< bn;j++)
        {
            if(b[i][1]>b[j][1])
            {
                t1=b[i][0];t2=b[i][1];
                b[i][0]=b[j][0];b[i][1]=b[j][1];
                b[j][0]=t1;b[j][1]=t2;   
            }    
        }   
    }    

 public static void main(String[] args) {   
    Scanner sc = new Scanner(System.in);   
    int i,j,cn,t1,t2,l1,l2,sum1,sum2;
    while(sc.hasNext()){
        cn=sc.nextInt();
        if(cn==0) break;
        an=0;bn=0;
        for(i=0;i< cn;i++)
        {
            t1=sc.nextInt();
            t2=sc.nextInt();
            if(t1<=t2)
            {
                a[an][0]=t1;a[an][1]=t2;
                an++;
            }    
            else
            {
                b[bn][0]=t1;b[bn][1]=t2;
                bn++;
            }
        }    
        sort();
        for(i=0;i< bn;i++)
        {
            a[an][0]=b[i][0];a[an][1]=b[i][1];
            an++;
        }        
        l1=l2=0;sum1=sum2=0;
  
        for(i=0;i< an;i++)
        {
            sum1+=a[i][0];
            if(sum1>sum2)sum2=sum1;
            sum2+=a[i][1];
        }    
        System.out.printf("%d\n",sum2);
    }    
  }
}

  1. 第23行:
    hash = -1是否应该改成hash[s ] = -1

    因为是要把从字符串s的start位到当前位在hash中重置

    修改提交后能accept,但是不修改居然也能accept

  2. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!

  3. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!

  4. 问题3是不是应该为1/4 .因为截取的三段,无论是否能组成三角形, x, y-x ,1-y,都应大于0,所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.