題目#
有 \(n\) \((1 \leq n \leq 50)\) 個區間，第 \(i\) 個為 \([l_i, r_i]\) \((-2 \times 10^9 \leq l \leq r \leq 2 \times 10^9)\)
可以將每個區間中的整數丟到一個陣列裡面，將陣列排序以後，請求出此陣列中第 \(k\) 個數（從 0 開始）
解題思路#
如果直接模擬題目操作的話太慢了。因為題目問第 \(k\) 個數，不難聯想到「第 \(k\) 大二分搜」。
我們可以對於答案做二分搜，並對於每一個答案檢查小於等於那個數的數字個數是否小於等於 \(k\)，並用這個值更新搜索範圍。
時間複雜度： \(O(n \times log(max(r) - max(l)))\)
常見錯誤#
- 是從「0」開始，不是從「1」開始
- 有一些（很多）東西需要開 long long，只開 int 的話有機會 overflow（如果想知道自己是不是因為這個 bug WA 可以加一行
#define int long long。 - \(l\) 到 \(r\) 會有 \((r - l + 1)\) 個數字
完整程式碼#
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<pair<long long, long long>> v(n);
for (int i = 0; i < n; i++) {
cin >> v[i].first >> v[i].second;
}
long long l = -2e9, r = 2e9;
while (l < r){
long long m = (l + r - 1) / 2;
long long cnt = 0;
for (int i = 0; i < n; i++) {
cnt += min(v[i].second + 1, m + 1) - min(v[i].first, m + 1);
}
if (cnt <= k) {
l = m + 1;
}
else{
r = m;
}
}
cout << l << "\n";
}
