CSES – Apartments

題目連結

題意

給 n 個人跟 m 個公寓跟一個數字 k。第 i 個公寓的大小用 b[i] 表示。第 i 個人會接受大小在 (a[i] – k, a[i] + k) 以內的公寓。問有幾個人可以拿到公寓？

解題想法

先將兩個陣列由小到大排序利用兩個指標p1及p2模擬分配的情況。

每次我們比較 a[p1] 是否能夠配對 b[p2]，如果符合我們就配對。

如果不能配對的話 (a[p1] – b[p1] > k):
如果 a[p1] < b[p2] 把 p1 往後一個，反之把 p2 往後一個。

假如 a[p1] < b[p2]，距離 a[p1] 最近的 b[p2] 已經太大了，那之後的 b[p2] 也只會越來越大，所以 a[p1] 已經確定配不到了，因此可以直接跳過。
a[p1] > b[p2] 可以直接 p2++ 也是相同的邏輯

#include <bits/stdc++.h>
using namespace std;
int main(){    
    int n, m, k;
    cin >> n >> m >> k;
    vector <int> a(n);
    vector <int> b(m);
    for(int &x : a) cin >> x;
    for(int &x : b) cin >> x;
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    int p1 = 0, p2 = 0;
    int ans = 0;
    while(p1 < n && p2 < m){
        if(abs(a[p1]-b[p2]) <= k){ //成功配對 
            p1++;
            p2++;
            ans++;
        } else { //沒有成功配對
            if(a[p1] < b[p2]) p1++; 
            else p2++;
        }
    }
    cout << ans << '\n';
}