[AtCoder] ABC 127 D – Integer Cards

問題

方針

実際にカードを書き換えていく方法は計算量が多くなるので、最終的なカードの値を考えていきます。

ある操作でカードを書き換えるのではなく、カードが増えたとして、上から \( N \) 枚選び、その和が答えになります。ここで、マップを考えます。キーにカードの取りえる値、バリューにカードの枚数を保持するようなマップをキーの降順になるように並び替えます。

全体として、カードが

\[ N + \displaystyle \sum_{i=1}^{M} B_i\]

枚あるイメージですね。

コード

提出したコード

マップによるカードの管理

  map<ll, ll, greater<ll>> m;
  for (int i = 0; i < N; i++) {
    m[A[i]]++;
  }
  for (int i = 0; i < M; i++){
    m[C[i]] += B[i];
  }
  ll ans = 0;
  ll cnt = 0;
  for (auto i = m.begin(); i != m.end(); i++) {
    if (cnt > N) break;
    if (cnt + i -> second >= N) {
      ans += (N - cnt) * i -> first;
      break;
    } else {
      ans += i -> second * i -> first;
      cnt += i -> second;
    }
  }