有一只蝸牛位于二維坐標系的原點(0,0)，在x軸上有n根平行于y軸的竹竿，它們底部的縱坐標為0，橫坐標分別為x_1,x_2,\cdots,x_n。蝸牛想要從原點走到第n根竹竿的底部(x_n,0)。蝸牛在x軸上的移動速度是1單位每秒，在竹竿上向上爬的速度是0.7單位每秒，向下爬的速度是1.3單位每秒。此外，蝸牛可以在第i根竹竿的高度為a_i的位置(x_i,a_i)瞬間傳送到第i + 1根竹竿的高度為b_{i+1}的位置(x_{i+1},b_{i+1})（0 < i < n）。
?
輸入格式
?
1.?第一行是一個正整數n。
2.?第二行是n個正整數x_1,x_2,\cdots,x_n。
3.?后面n-1行，每行兩個正整數a_i,b_{i+1}。
?
輸出格式
?
輸出一行，一個浮點數表示蝸牛到達目的地所需的最少時間（四舍五入保留兩位小數）。
?
樣例輸入
?
plaintext
??
3
1 10 11
1 1
2 1
?
?
import java.util.Scanner;
public class SnailPath {
? ? public static void main(String[] args) {
? ? ? ? Scanner scanner = new Scanner(System.in);
? ? ? ? int n = scanner.nextInt();
? ? ? ? int[] x = new int[n];
? ? ? ? for (int i = 0; i < n; i++) {
? ? ? ? ? ? x[i] = scanner.nextInt();
? ? ? ? }
? ? ? ? int[][] ab = new int[n - 1][2];
? ? ? ? for (int i = 0; i < n - 1; i++) {
? ? ? ? ? ? ab[i][0] = scanner.nextInt();
? ? ? ? ? ? ab[i][1] = scanner.nextInt();
? ? ? ? }
? ? ? ? double minTime = Double.MAX_VALUE;
? ? ? ? for (int state = 0; state < (1 << (n - 1)); state++) {
? ? ? ? ? ? double time = 0;
? ? ? ? ? ? int pos = 0;
? ? ? ? ? ? int height = 0;
? ? ? ? ? ? for (int i = 0; i < n - 1; i++) {
? ? ? ? ? ? ? ? if ((state & (1 << i))!= 0) {
? ? ? ? ? ? ? ? ? ? // 使用傳送門
? ? ? ? ? ? ? ? ? ? if (height!= 0) {
? ? ? ? ? ? ? ? ? ? ? ? time += (double) height / 0.7;
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? time += 0;
? ? ? ? ? ? ? ? ? ? height = ab[i][1];
? ? ? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? ? ? // 不使用傳送門
? ? ? ? ? ? ? ? ? ? if (height!= 0) {
? ? ? ? ? ? ? ? ? ? ? ? time += (double) height / 0.7;
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? height = 0;
? ? ? ? ? ? ? ? ? ? time += (double) (x[i + 1] - x[i]);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? ? ? if (height!= 0) {
? ? ? ? ? ? ? ? time += (double) height / 0.7;
? ? ? ? ? ? }
? ? ? ? ? ? time += (double) x[n - 1];
? ? ? ? ? ? if (time < minTime) {
? ? ? ? ? ? ? ? minTime = time;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? System.out.printf("%.2f", minTime);
? ? }
}
解題思路
?
1.?初始化：
- 首先讀取輸入的n，竹竿的橫坐標數組x，以及每對傳送門的高度a和b。
- 初始化一個變量?min_time?為一個較大的值，用于記錄最小時間。
2.?計算時間：
- 對于每一種可能的路徑，計算蝸牛從原點到達第n根竹竿底部所需的時間。
- 路徑可以分為以下幾種情況：
- 蝸牛一直沿著x軸爬行，不使用任何傳送門。這種情況下，時間為x_n。
- 蝸牛使用部分傳送門。在這種情況下，需要考慮每一種可能的傳送門組合。
- 對于每一對相鄰的竹竿i和i+1，計算以下兩種情況的時間：
- 從x_i沿著x軸爬行到x_{i+1}的時間，即x_{i+1}-x_i。
- 從x_i處的高度a_i傳送到x_{i+1}處的高度b_{i+1}，然后計算在竹竿上移動的時間。在竹竿上向上爬的時間為a_i/0.7，向下爬的時間為b_{i+1}/1.3，傳送時間為0（瞬間傳送）。
- 選擇時間最短的路徑。
3.?更新最小時間：
- 對于每一種可能的路徑，計算出時間后，更新?min_time?為較小的值。
4.?輸出結果：
- 最后輸出?min_time?，四舍五入保留兩位小數。
還是不太理解o-0
)
