題意#
題目給定 \( n \) 個申請人與 \( m \) 間空公寓。
每個申請人有理想的公寓大小，並接受大小差距在 \( k \) 以內的房屋（即介於理想大小 \( -k \) 到 \( +k \) 之間）。
我們需要求出最多能滿足幾位申請人。
思路#
為了讓盡可能多的人配對成功，我們可以將「申請人的預期大小」和「公寓的實際大小」分別從小到大排序。
排序後，利用雙指標（Two Pointers）來進行配對：一個指標指向申請人，另一個指向公寓。
- 如果目前公寓小於申請人的底線，代表這間公寓無法滿足後續的申請人，直接換下一間公寓。
- 如果公寓大於申請人的接受上限，代表此申請人無法接受後面的公寓，換下一位申請人。
- 如果公寓大小落在申請人的接受範圍內，則成功配對，兩個指標同時前進，並將配對數加一。
這種貪婪策略能確保我們從需求小的物件開始配對，逐步滿足申請人，避免浪費配對機會。
程式碼#
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>
signed main() { WA();
int n, m, k; cin >> n >> m >> k;
deque<int> a(n), b(m);
for (auto &i : a) cin >> i;
for (auto &i : b) cin >> i;
// 將申請人要求與公寓大小各自從小到大排序
sort(all(a)); sort(all(b));
int cnt = 0;
// 使用雙指標同時遍歷申請人 (adx) 與公寓 (bdx)
for (int adx = 0, bdx = 0; adx < n && bdx < m;) {
// 如果當前公寓加上寬容度後還是小於申請人的理想值，代表公寓太小，換下一間
if (b[bdx]+k < a[adx]) bdx++;
// 如果公寓減去寬容度後還是大於理想值，代表公寓太大，換下一個要求較高的申請人
else if (b[bdx]-k > a[adx]) adx++;
// 成功落在接受範圍內，將兩人配對，指標同時前進
else adx++, bdx++, cnt++;
}
// 輸出最多能成功配對的數量
cout << cnt << '\n';
}
