3 条题解

  • 1
    @ 2026-4-10 15:07:53

    如果要确定a在序列中出现的次数是否大于等于b,且b出现的次数大于等于a,可以创建一个数组来统计出现数字的次数,然后再对每一个数字的次数进行维护。

    注意到数字a的出现的次数肯定在 [1,cnt[a]] 的范围内,那就可以确定可能的b肯定也在1到cnt[a]的范围内,因此对该区间内的数做一个判断,即判断区间内出现的数字的出现次数是否大于等于a即可。

    #include <bits/stdc++.h>
    #define all(x) (x).begin(), (x).end()
    #define pb push_back
    #define pf push_front
    using namespace std;
    using ll = long long;
    using ull = unsigned long long;
    typedef pair<int, int> P;
    const int mod = 998244353;
    const int MOD = 1e9 + 7;
    
    void solve()
    {
        int n;
        cin >> n;
        vector<int> cnt(n + 1); // 统计读入的数的出现次数
        for (int i = 1; i <= n; i++)
        {
            int ai;
            cin >> ai;
            cnt[ai]++;
        }
        int ans = 0;
        for (int i = 1; i <= n; i++)
        {
            if (!cnt[i])
                continue;
            for (int j = 1; j <= cnt[i]; j++)
            {
                if (cnt[j] >= i) // 判断数字次数是否大于等于a
                    ans++;
            }
        }
        cout << ans << endl;
    }
    
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        int T = 1;
        //    cin >> T;
        while (T--)
        {
            solve();
        }
        return 0;
    }
    

    信息

    ID
    598
    时间
    1000ms
    内存
    256MiB
    难度
    7
    标签
    递交数
    167
    已通过
    43
    上传者