题解 | 小红的数组清空（空当接龙喵）

直接模拟喵，就类似空当接龙喵，你理解的吧喵

我们先排序，这样就确保了不会出现先把2放进牌组，但是后面又出现1的情况

我们需要找到对于每个a[i]，我们都要找到有没有a[i] - 1能接上的喵

对于这样的查找，我们最好每次都能logn找到喵

这样一来喵，我们选multiset就是一个最好的选择了喵

玩空当接龙最后的牌组数就是我们的答案了喵

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int MOD = 998244353;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 1e6 + 10;
//#define int long long

void solve()
{
    int n;
    cin>>n;
    vector<int> a(n + 1);
    for (int i = 1 ; i <= n ; i++) cin>>a[i];
    sort(a.begin() + 1,a.end());
    multiset<int> st;
    for (int i = 1 ; i <= n ; i++)
    {
        auto it = st.find(a[i] - 1);
        if (it == st.end())
        {
            st.insert(a[i]);
        }
        else
        {
            st.erase(it);
            st.insert(a[i]);
        }
    }
    cout<<st.size()<<'\n';
    return;
}
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int _ = 1;
    //std::cin>>_;
    while (_--)
    {
        solve();
    }
    return 0;
}