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)\) 个数，且不能重复使用。

思路

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

1
2
3
4
5
6
7
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\)，我们就损失了一组匹配。所以找位置靠后的匹配一定不劣。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#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;
}

The End