题解：P17147 [ICPC 2017 Xi'an R] Lovers

· · 题解

P17147 [ICPC 2017 Xi'an R] Lovers 题解

思路

贪心。我们让女孩从小到大排，男孩从大到小排。让最小的女孩去配当前最大的男孩，配不上就说明这个女孩和谁都配不上，扔了；配得上就计数器加一，然后双方都往后移。

证明：最小的女孩如果能配某个男孩，那她配当前最大的男孩一定也能配，而且把最大的男孩留给她不会比留给别人更差。所以这样贪心是对的。 ::::success[code]


#include <bits/stdc++.h>
using namespace std;

#define int long long
#define endl '\n'
const int N = 2e5 + 7;

int n, k;
int a[N], b[N];

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T;
    cin >> T;
    while(T --){
        cin >> n >> k;
        for(int i = 1; i <= n; i ++) cin >> a[i];
        for(int i = 1; i <= n; i ++) cin >> b[i];

        sort(a + 1, a + 1 + n);
        sort(b + 1, b + 1 + n, greater<int>());

        int l = 1, r = 1, ans = 0;
        while(l <= n && r <= n){
            if(a[l] + b[r] >= k){
                ans ++;
                l ++;
                r ++;
            }
            else l ++;
        }

        cout << ans << endl;
    }

    return 0;
}