题解：P15138 [SWERC 2025] Dungeon Equilibrium

Ethan_sun · 2026-02-03 13:51:53 · 题解

P15138 [SWERC 2025] Dungeon Equilibrium

solution

简单题。

我们开一个数组记录 a_i 种怪物的出现次数，之后对其分讨。

::::info[第 i 种怪物出现次数比 i 小时]{open} 答案需加上怪物的出现次数。 ::::

::::info[第 i 种怪物出现次数等于 i 时]{open} 满足题目描述中的条件，无需更改答案。 ::::

::::info[第 i 种怪物出现次数比 i 大时]{open} 答案加上出现次数与 i 的差值。 ::::

做完了qwq。

AC code

#include <bits/stdc++.h>
#define debug(a) cerr << (#a) << " = " << (a) << endl;
#define int long long
#define maxn 100010
#define endl '\n'
using namespace std;

int n;
int max_a;
int a[maxn], cnt[maxn];
int solve() {
    int tot = 0;
    for (int i = 0; i <= max_a; i++) {
        if (cnt[i] < i) {
            tot += cnt[i];
        }
        else if (cnt[i] > i) {
            tot += (cnt[i] - i);
        }
    }
    return tot;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t; t = 1;
    while (t--) {
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            max_a = max(max_a, a[i]), cnt[a[i]]++;
        }
        cout << solve() << endl;
    }
    return 0;
}