AtCoder Regular Contest 082 C - Good Sequence

問題について考えたこと

問題文へ

正の整数列aを良い数列にするためには、要素が3ならば個数を3にする。取り除いた数の合計の最小値を求めよ。

このことから、整数ごとに個数を数えるためunordered_mapを使用しました。aiが最大でなので配列ではメモリを多く使ってしまいます。

各要素がその数より小さいか大きいかで、余分を取り除くかすべてを取り除くか変わります。

#define _GIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;


int main(void) {
  int N;
  cin >> N;
  unordered_map<int, int> ump;
  rep(i, N) {
    int a;
    cin >> a;
    ump[a]++;
  }

  ll ans = 0;
  for (auto itr = ump.begin(); itr != ump.end(); ++itr) {
    pair<int, int> elm = *itr;
    if (elm.first < elm.second) {
      ans += elm.second - elm.first;
    } else if (elm.second < elm.first) {
      ans += elm.second;
    }
  }

  cout << ans << endl;
  
  return 0;
}