题解：P12880 [蓝桥杯 2025 国 C] 数字配对

· · 题解

题意简述

给定 n 个正整数 a_1,\dots,a_n，满足 1 \le n, a_i \le 10^6。求满足 i < j 且 a_i+1=a_j 的 (i, j) 个数，且不能重复使用。

思路

拿到题第一时间可能会想到枚举每个数，只要前面有对应的数就直接匹配。比如：

for (int i = 1; i <= n; i++) {
    cin >> a[i];
    if (cnt[a[i]-1])
        cnt[a[i]-1]--, ans++;
    else
        cnt[a[i]]++;
}

但这样是错误的。当输入为 4 2 3 4 3 时，a_1 与 a_4 配对，a_2 与 a_3 配对，答案为 2，而程序输出为 1。我们发现，按原序列枚举的弊端是在我们处理一个数时，不知道后面还有没有相同的数。同时，a_i 与 n 同阶启发我们改变贪心策略，枚举每一个具体数值。

对每个数 a_i，开一个 vector 记录它在原序列中出现的每个位置。对于相邻的两个 vector，使用双指针统计答案，每个位置都尽量和最靠后的位置匹配。这样这道题就做完了。

感性证明：假设 a_i=x, a_j=a_k=x+1，i<j<k。如果我们将 a_i 与 a_j 匹配，若存在 l 满足 j<l<k, a_l = x+2，我们就损失了一组匹配。所以找位置靠后的匹配一定不劣。

代码

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

const int N = 1e6+5;
vector<int> cnt[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, mx = 0, ans = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        cnt[x].push_back(i);
        mx = max(mx, x);
    }
    n = mx;
    for (int i = 2; i <= n; i++) {
        int j = cnt[i-1].size()-1, k = cnt[i].size()-1;
        while (j >= 0 && k >= 0) {
            while (j > 0 && cnt[i-1][j] > cnt[i][k])
                j--;
            if (cnt[i-1][j] > cnt[i][k]) break; // 此时cnt[i-1]枚举完了
            while (k > 0 && j > 0 && cnt[i-1][j] < cnt[i][k])
                ans++, k--, j--, cnt[i].pop_back(); // 删除对应位置，避免下次循环重复计算
            if (cnt[i-1][j] < cnt[i][k]) { // 此时cnt[i]枚举完了
                ans++, cnt[i].pop_back();
                break;
            }
        }
    }
    cout << ans << endl;
    return 0;
}