CF1790D Matryoshkas 题解
Qiu_chen
·
·
题解
思路
这道题可以直接用map。
每输入一个数 $map$ 中相对应的元素加 $1$ 。
随后将整个数组排序，每次从尾到头搜索，每次检测 $map$ 中是否存在比当前数小 $1$ 就行了。
~~剩下不用多说了吧~~
# 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
void solve(){
int n;
cin>>n;
map<int ,int> mp;
for(int i=1;i<=n;i++){
int num;
cin>>num;
mp[num]++;
}
int ans=0;
for(auto it3=mp.begin();it3!=mp.end();it3++){
if(it3->second>0){
while(mp[it3->first]>0){
auto it=it3;
mp[it->first]--;
ans++;
auto it2=it;
it++;
if(it==mp.end()) continue;
while(it2->first==it->first-1&&mp[it->first]>0){
mp[it->first]--;
it2++;it++;
if(it==mp.end()) continue;
}
}
}
}
cout<<ans<<endl;
}
int main(){
int a;
cin>>a;
for(int i=1;i<=a;i++){
solve();
}
return 0;
}
```