<-点点赞资瓷一下作者hh
题目描述
某干脆面厂商在每包面中都放置有一张武将卡。
武将卡共分为 $n$ 种,编号 $1∼n$。
当集齐 $1∼n$ 号武将卡各一张时,就可以拿它们去换大奖。
为了换大奖,李华先后购买了 $m$ 包该品牌的干脆面。
其中第 $i$ 包面中包含的武将卡的编号为 $a[i]$。
每当买完一包面,得到该面赠送的武将卡后,李华都会审视一遍自己手中的全部卡牌。
如果此时自己现有的卡牌能够凑齐全部武将卡,那么他就会立即将每种武将卡都拿出一张,并将拿出的卡牌寄给厂商,用来换奖。
请你分析李华购买干脆面的整个过程并计算购买完每一包面后,李华能否凑齐全部武将卡用来换奖。
注意,每次换奖都需要消耗卡牌,消耗掉的卡牌就不属于他了。
输入格式
第一行包含两个整数 $n,m$。
第二行包含 $m$ 个整数 $a[1],a[2],…,a[m]$。
输出格式
输出一个长度为 $m$ 的 $01$ 字符串,如果买完第 $i$ 包面后,李华能够凑齐全部武将卡用来换奖,则第 $i$ 位字符为 $1$,否则为 $0$。
数据范围
前 $5$ 个测试点满足 $1≤n,m≤20$。
所有测试点满足 $1≤n,m≤10^5,1≤a[i]≤n$。
输入样例1:
3 11
2 3 1 2 2 2 3 2 2 3 1
输出样例1:
00100000001
输入样例2:
4 8
4 1 3 3 2 3 3 3
输出样例2:
00001000
为了误导帮助新手,先来解释一下思路。
用 $b$ 数组统计卡牌个数,一旦出现前面没有出现的卡牌,计数器 $cnt++$,只要 $cnt == n$,就代表着一次卡片集全,输出 $1$,且将 $b$ 的每个数组元素减一,若减去后的数组元素等于 $0$,$cnt- -$,否则输出 $0$。
C++代码
#include <bits/stdc++.h>
using namespace std;
int a, b[100010];
int main () {
int n, m, cnt = 0;
cin >> n >> m;
for (int i = 1; i <= m; i++){
cin >> a;
b[a] ++;
if (b[a] == 1) cnt ++;
//若 a 只出现了这一次,就多了一个从前没出现的数
if (cnt == n){//所有数都出现过
cout << 1;
for (int j = 1; j <= n; j++){
b[j] --;
if (b[j] == 0) cnt --;
//如果这个数用掉了,这个数 j 等于没有出现
}
}
else cout << 0;
}
return 0;
}
//完结撒花
$cnt-\-$
加一个空格就好了,对吧no
$cnt-\-$
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
一遍懂
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%
$O(m)$解法
这是什么神仙思路orz
大佬您能解释一下吗
https://www.acwing.com/file_system/file/content/whole/index/content/6235964/
这时间复杂度居然能过吗😂😂我还以为过不去,想了半天😅😅
1890 ms
看来有必要要相信自己hh
时间复杂度m * 2 ,最多有m/n 套牌,每套对于计数数组减1的时候循环n次总共m/n * n == n !!!
woc大佬思路NB
大哥牛杯
stO