← 返回 meta 的题目列表Plan Round Trip With Minimum Flight Cost
类型：online_judge
Problem: Plan Round Trip With Minimum Flight Cost
You are given two integer arrays of the same length:
D[i] is the departure flight cost on day i;
R[i] is the return flight cost on day i.
Choose a departure day i and a return day j such that:
0 <= i < j < n
That is, the departure day must be earlier than the return day.
Find the round trip with the minimum total cost:
cost = D[i] + R[j]
Return the departure index, the return index, and the minimum cost.
If multiple plans have the same minimum cost, break ties as follows:
Choose the earliest departure day, meaning the smaller i;
If the departure day is also the same, choose the latest return day, meaning the larger j.
First describe an O(n^2) approach, then implement an optimized O(n) solution.
Input Format
n
D[0] D[1] ... D[n-1]
R[0] R[1] ... R[n-1]
Output Format
depart_index return_index min_cost
Use 0-based index.
Constraints
2 <= n <= 200000
0 <= D[i], R[i] <= 10^9
Example
Input:
5
10 7 8 3 6
5 4 10 7 5
Output:
3 4 8
Explanation: Depart on day 3 with cost D[3] = 3, and return on day 4 with cost R[4] = 5. The total cost is 8.
Example
Input
5
10 7 8 3 6
5 4 10 7 5
Output
3 4 8