首页 > 专题系列 > Java解POJ > POJ 2744 Atomic Car Race [解题报告] Java
2013
11-11

POJ 2744 Atomic Car Race [解题报告] Java

Atomic Car Race

问题描述 :

In the year 2020, a race of atomically energized cars will be held. Unlike today’s car races, fueling is not a concern of racing teams. Cars can run throughout the course without any refueling. Instead, the critical factor is tire (tyre). Teams should carefully plan where to change tires of their cars.

The race is a road race having n checkpoints in the course. Their distances from the start are a1, a2, …, and an (in kilometers). The n-th checkpoint is the goal. At the i-th checkpoint (i < n), tires of a car can be changed. Of course, a team can choose whether to change or not to change tires at each checkpoint. It takes b seconds to change tires (including overhead for braking and accelerating). There is no time loss at a checkpoint if a team chooses not to change tires.

A car cannot run fast for a while after a tire change, because the temperature of tires is lower than the designed optimum. After running long without any tire changes, on the other hand, a car cannot run fast because worn tires cannot grip the road surface well. The time to run an interval of one kilometer from x to x + 1 is given by the following expression (in seconds). Here x is a nonnegative integer denoting the distance (in kilometers) from the latest checkpoint where tires are changed (or the start). r, v, e and f are given constants.
    1/(v – e * (x – r)) (if x >= r)

    1/(v – f * (r – x)) (if x < r)

Your mission is to write a program to determine the best strategy of tire changes which minimizes the total time to the goal.

输入:

The input consists of multiple datasets each corresponding to a race situation. The format of a

dataset is as follows.

n

a1 a2 . . . an

b

r v e f

The meaning of each of the input items is given in the problem statement. If an input line contains two or more input items, they are separated by a space.

n is a positive integer not exceeding 100. Each of a1, a2, …, and an is a positive integer satisfying 0 < a1 < a2 < . . . < an <= 10000. b is a positive decimal fraction not exceeding 100.0. r is a nonnegative integer satisfying 0 <= r <= an - 1. Each of v, e and f is a positive decimal fraction. You can assume that v - e * (an - 1 - r) >= 0.01 and v – f * r >= 0.01.

The end of the input is indicated by a line with a single zero.

输出:

For each dataset in the input, one line containing a decimal fraction should be output. The decimal fraction should give the elapsed time at the goal (in seconds) when the best strategy is taken. An output line should not contain extra characters such as spaces.

The answer should not have an error greater than 0.001. You may output any number of digits after the decimal point, provided that the above accuracy condition is satisfied.

样例输入:

2
2 3
1.0
1 1.0 0.1 0.3
5
5 10 15 20 25
0.15
1 1.0 0.04 0.5
10
1783 3640 3991 4623 5465 5481 6369 6533 6865 8425
4.172
72 59.4705 0.0052834 0.0611224
0

样例输出:

3.5397
31.9249
168.6682

解题代码:

/* @author: */
import java.util.Scanner;   
public class Main {   
   
 public static void main(String[] args) {   
 Scanner sc = new Scanner(System.in);   
    double b,v,e,f,t[]=new double[101],t1;
    int n,a[]=new int[101],r;
    int i,j,k,dis;
    while(sc.hasNext())
    {
        n=sc.nextInt();
        if(n==0) break;

        a[0]=0;
        for(i=1;i<=n;i++)
           a[i]=sc.nextInt();
        
        b=sc.nextDouble();
        r=sc.nextInt();
        v=sc.nextDouble();
        e=sc.nextDouble();
        f=sc.nextDouble();

        t[0]=0; 
        for(i=0;i< n;i++)
        {
            if(i==0)t1=0;else t1=b;
            for(j=i+1;j<=n;j++)
            {
                for(k=a[j-1];k< a[j];k++)
                {
                    dis=k-a[i];
                    if(dis>=r) t1+=1/(v-e*(dis-r));
                    else t1+=1/(v-f*(r-dis));
                }    
                if(i==0||t1+t[i]< t[j])t[j]=t[i]+t1;
            }    
        }      
        System.out.printf("%.4f\n",t[n]);
    }    
   }
}

  1. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.

  2. 我没看懂题目
    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
    不知道题目例子是怎么得出来的