3 条题解
-
1
如果要确定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
- 上传者