P16816 [蓝桥杯 2026 国 Python B] 贴纸册交换 题解

C++ 题解。

题目传送门

题意

有 \(N\) 种贴纸，编号 \(1\) 到 \(N\)。按顺序得到 \(M\) 张贴纸，第 \(i\) 张编号为 \(A_i\)。

  • 如果没收集过 \(A_i\)，就贴上。
  • 如果收集过 \(A_i\)，就变成 \(1\) 张交换券。
  • 如果凑够 \(K\) 张券，立刻换当前编号最小且没收集的贴纸。

问最后收集了多少种。

思路

直接模拟即可。

用 \(sum\) 记录已收集种类数，\(s\) 记录当前券数。

如果每次兑换都从 \(1\) 开始找最小缺失会 超时，可以用一个指针 \(p\) 记录当前可能的最小缺失编号。

代码

#include 
#define Jason227 return
#define Code 0
using namespace std;const int MAXN = 200010, MAXM = 200010;
int N, M, K, A[MAXM], s = 0, sum = 0, p = 1;
bool B[MAXN];int main(){cin >> N >> M >> K;for(int i = 1; i <= M; i++){cin >> A[i];if(B[A[i]]){s++;if(s == K){for(int j = p; j <= N; j++){if(!B[j]){s = 0, sum++, p = j;B[j] = true;break;}}}}else{B[A[i]] = true;sum++;}}cout << sum << '\n';Jason227 Code;
}

复杂度分析

  • 时间复杂度：\(O(N + M)\)。每个贴纸处理一次，指针 \(p\) 总共右移不超过 \(N\) 次。
  • 空间复杂度：\(O(N + M)\)。存贴纸数组和标记数组。

AC 记录