題目#
有兩個陣列 \(a\) 和 \(b\)，各自包含 \(n\) 個正整數。對於每一組 \((i, j)\) \((1 \leq i, j \leq n)\)，將 \(a_i + b_j\) 放到陣列中。請求出此陣列中第 \(k\) 小的數字。
解題思路#
按照題目暴力模擬時間複雜度 \(O(n^2)\)，不太可行，我們可以試試對答案二分搜。
對於一個答案 \(ans\)，將 \(a\) 和 \(b\) 排序好後，用雙指針， \(p1\) 指向 \(1\)、 \(p2\) 指向 \(n\)。當 \(p1\) 增加的時候，重複 p2-- 直到 \(a_{p1} + b_{p2} \leq ans\)。維護一個變數 \(cnt\)，代表有多少個配對 \(\leq ans\)。每次改變完 \(p2\) 後， \(cnt\) 就加上 \(p2\)。最後檢查 \(cnt\) 是否 \(\geq k\) 後縮小範圍區間。
常見錯誤#
- 要記得 \(k\) 和 \(cnt\) 要開 long long，不然有機會 overflow
- \(l\) 和 \(r\) 有些寫法 (例如 \(m = (l + r) / 2\)）需要開 long long
- 大於 / 大於等於 / 小於 / 小於等於 要弄對
- 上面的解題思路是 1 based，但是範例程式碼是 0 based，有些地方要多 \(+1\)
題外話#
這題和 TOI 2023 的 pB 裁員風暴 很像，寫完這題可以寫寫看。
完整程式碼#
#include <bits/stdc++.h>
using namespace std;
signed main(){
long long n, k;
cin >> n >> k;
vector<int> a(n), b(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 0; i < n; i++) {
cin >> b[i];
}
sort(a.begin(), a.end());
sort(b.begin(), b.end());
int l = 0, r = 2e9;
while (l < r) {
int m = l + (r - l) / 2;
int p2 = n - 1;
long long cnt = 0;
for (int p1 = 0; p1 < n; p1++) {
while (p2 != -1 && a[p1] + b[p2] > m) {
p2--;
}
cnt += p2 + 1;
}
if (cnt < k) {
l = m + 1;
}
else{
r = m;
}
}
cout << l << "\n";
}
