最小花费
在某条线路上有N个火车站,有三种距离的路程,L1,L2,L3,对应的价格为C1,C2,C3.其对应关系如下:
距离s
票价
0<S<=L1 C1
L1<S<=L2 C2
L2<S<=L3 C3
输入保证0<L1<L2<L3<10^9, 0<C1<C2<C3<10^9。
每两个站之间的距离不超过L3。 当乘客要移动的两个站的距离大于L3的时候,
可以选择从中间一个站下车,然后买票再上车,所以乘客整个过程中至少会买两张票。
现在给你一个 L1,L2,L3,C1,C2,C3。然后是A B的值,其分别为乘客旅程的起始站和终点站。
然后输入N,N为该线路上的总的火车站数目,然后输入N-1个整数,分别代表从该线路上的第一个站,到第2个站,第3个站,……,第N个站的距离。
根据输入,输出乘客从A到B站的最小花费。
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int l1 = in.nextInt();
int l2 = in.nextInt();
int l3 = in.nextInt();
int c1 = in.nextInt();
int c2 = in.nextInt();
int c3 = in.nextInt();
int a = in.nextInt();
int b = in.nextInt();
int n = in.nextInt();
int[] nums = new int[n];
for(int i=1;i<n;i++){
nums[i] = in.nextInt();
}
int[] dp = new int[n];
for(int i=a;i<b;i++){
int index = find(nums, a-1, i, l3);
dp[i] = dp[index] + c3;
index = find(nums, a-1, i, l2);
dp[i] = Math.min(dp[i], dp[index] + c2);
index = find(nums, a-1, i, l1);
dp[i] = Math.min(dp[i], dp[index] + c1);
}
System.out.println(dp[b-1]);
}
public static int find(int[] nums, int left, int right, int num){
int mid = 0;
int max = nums[right];
while(left <= right){
mid = (left+right)>>1;
if(max - nums[mid] > num){
left = mid+1;
}else if(max - nums[mid] < num){
right = mid -1;
}else{
return mid;
}
}
return left;
}
}