洛谷P17147题解

分析

题意

一共有 $n$ 个女生、$n$ 个男生。

女生拥有权值数组 $a$，男生拥有权值数组 $b$。

规定：当 $a_i+b_j \ge k$ 时，女孩 $i$ 和男孩 $j$ 可以配对，且每个人最多只能匹配一次。

求最多能够配成多少对。

思路

1. 将 $a, b$ 升序排序。

2. 定义双指针：

   • $i$：$a$ 右指针，初始 $i=n-1$，从最大女生向左遍历；
   • $j$：$b$ 左指针，初始 $j=0$，指向剩余最小男生。

3. 双指针规则：

   • 如果 $a_i + b_j \ge k$：形成一对，$ans+1$，$i$ 左移，$j$ 右移；
   • 如果不足 $k$：当前最小男生无法匹配任何人，仅 $i$ 左移。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 5;
ll a[MAXN], b[MAXN];
int main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        ll k;
        cin >> n >> k;
        for (int i = 0; i < n; i++) cin >> a[i];
        for (int i = 0; i < n; i++) cin >> b[i];
        sort(a, a + n);
        sort(b, b + n);
        int l = 0, r = n - 1;
        int ans = 0;
        while (l < n && r >= 0) {
            if (a[l] + b[r] >= k) {
                ans++;
                l++;
                r--;
            } 
            else l++;
        }
        cout << ans << endl;
    }
    return 0;
}