← 返回 uber 的题目列表Minimum Delivery Cost Between Cities
类型：online_judge
Minimum Delivery Cost Between Cities
There are n cities, where city i has value deliveryCharge[i]. The distance between cities i and j is:
abs(deliveryCharge[i] - deliveryCharge[j])
A delivery from city i to city j can use either:
A normal delivery with cost abs(deliveryCharge[i] - deliveryCharge[j]).
A nearest-city delivery with cost 1, if j is the unique nearest other city to i.
For every query [start, end], return the minimum delivery cost from start to end. Intermediate cities may be used.
Input uses 1-indexed city IDs. The original prompt did not provide constraints; do not explicitly materialize all O(n²) edges.
Example
Input
3 2
1 10 20
1 3
2 3
Output
11
10