Có \(N\) chiếc xe, đánh số từ \(0\) đến \(N-1\), nằm trên một trục số. Bạn được cho danh sách vị trí

và danh sách mức tiêu hao nhiên liệu trên mỗi đơn vị quãng đường

Cả hai danh sách đều được sắp xếp không giảm. Tuy nhiên, bạn không biết chiếc xe nào ứng với vị trí nào hoặc mức tiêu hao nào. Bạn chỉ biết mỗi xe có đúng một vị trí và đúng một mức tiêu hao.

Tương đương, tồn tại hai hoán vị \(P,Q\) độ dài \(N\) sao cho xe thứ \(i\) ở vị trí \(X[P[i]]\) và có mức tiêu hao \(C[Q[i]]\).

Trong bài này, một hoán vị \(P\) độ dài \(N\) là một mảng thỏa mãn \(0\le P[i]\le N-1\) với mọi \(0\le i<N\), và \(P[i]\ne P[j]\) với mọi \(0\le i<j<N\). Chẳng hạn, \([2,1,0]\) là một hoán vị độ dài \(3\), còn \([1,2,3]\) và \([2,0,2]\) thì không.

Với một cách gán \((P,Q)\), tổng chi phí nhiên liệu để tập hợp tất cả xe tại điểm \(y\) là

Với một điểm nguyên \(p\), định nghĩa chi phí trong trường hợp xấu nhất tại \(p\) là tổng chi phí lớn nhất trên mọi cách gán có thể:

Hãy tìm một điểm nguyên \(p\) làm nhỏ nhất \(\operatorname{worst}(p)\). Nếu có nhiều điểm cùng đạt giá trị nhỏ nhất, có thể trả về bất kỳ điểm nào.

Yêu cầu cài đặt

Bạn cần cài đặt hàm sau:

int car_gathering(int N, std::vector<int> X, std::vector<int> C);

• \(N\) là số xe.
• \(X\) là mảng độ dài \(N\) chứa các vị trí xe, đã được sắp xếp không giảm.
• \(C\) là mảng độ dài \(N\) chứa các mức tiêu hao nhiên liệu, đã được sắp xếp không giảm.
• Hàm được gọi đúng một lần trong mỗi test.
• Hàm phải trả về một điểm nguyên \(p\) làm nhỏ nhất chi phí trong trường hợp xấu nhất.

Bài nộp không được cài đặt hàm main và phải khai báo #include "gather.h".

Giới hạn

• \(1\le N\le 10\,000\,000\).
• \(-10^9\le X[i]\le 10^9\) với mọi \(0\le i<N\).
• \(0\le C[i]\le 100\) với mọi \(0\le i<N\).
• \(X[i]\le X[j]\) và \(C[i]\le C[j]\) với mọi \(0\le i<j<N\).

Chấm điểm

Ví dụ

Xét lời gọi:

car_gathering(3, [-1, 2, 3], [1, 1, 2])

Giả sử \(p=1\). Có thể chứng minh cách gán \(P=[0,1,2]\), \(Q=[2,1,0]\) tạo ra trường hợp xấu nhất:

Cũng có thể chứng minh \(p=1\) làm nhỏ nhất giá trị \(\operatorname{worst}(p)\). Vì vậy hàm phải trả về 1.

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu theo định dạng:

N
X[0] X[1] ... X[N - 1]
C[0] C[1] ... C[N - 1]

và in một số nguyên là giá trị do car_gathering trả về.

Nguồn: Southeast Asia Team Selection Test 2026, Ngày 2, bài Car Gathering.