题解：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)

个数，且不能重复使用。

思路

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

CPP

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

，我们就损失了一组匹配。所以找位置靠后的匹配一定不劣。

代码

CPP

#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;
}

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

文章操作

题意简述

思路

代码

相关推荐

评论

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