P76033 舞伴匹配 — 题解

专题： 双指针
适用题目： 新生 OJ 本地题包中的 P76033，不要直接用于外站同名题。

解题思路

先分别排序两组等级，再双指针配对：能匹配就都前进，否则跳过等级更小的一人。

复杂度

时间 $O(n\log n+m\log m)$，额外空间 $O(n+m)$。

易错点

等级差必须小于等于 1，不要求两人等级相同。

C11 参考程序

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <limits.h>

int cmp_ll_asc(const void *p, const void *q) {
    long long a = *(const long long *)p, b = *(const long long *)q;
    return (a > b) - (a < b);
}
int cmp_ll_desc(const void *p, const void *q) {
    long long a = *(const long long *)p, b = *(const long long *)q;
    return (b > a) - (b < a);
}

int main(void) {
    int n,m;scanf("%d",&n);
    long long *a=malloc(n*sizeof(long long));
    for(int i=0;i<n;i++)scanf("%lld",&a[i]);
    scanf("%d",&m);
    long long *b=malloc(m*sizeof(long long));
    for(int i=0;i<m;i++)scanf("%lld",&b[i]);
    qsort(a,n,sizeof(long long),cmp_ll_asc);
    qsort(b,m,sizeof(long long),cmp_ll_asc);
    int i=0,j=0,ans=0;
    while(i<n && j<m){
        if(llabs(a[i]-b[j])<=1){ans++;i++;j++;}
        else if(a[i]<b[j])i++;
        else j++;
    }
    printf("%d\n",ans);free(a);free(b);return 0;
}

C++17 参考程序

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define nl '\n'

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n;
    vector<int>a(n);
    for(auto &x:a)cin>>x;
    cin>>m;
    vector<int>b(m);
    for(auto &x:b)cin>>x;
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    int i=0,j=0,ans=0;
    while(i<n&&j<m){
        if(abs((ll)a[i]-b[j])<=1){
            ans++;
            i++;
            j++;
        }
        else if(a[i]<b[j])i++;
        else j++;
    }
    cout<<ans<<nl;
    return 0;
}

题解建议设置为训练结束后开放。普通判题无法验证是否实际使用指定函数或 STL。