AtCoder Beginner Contest 127 D - Integer Cards

考えたこと：

・愚直解として以下のようなものがある。

vectorを１つ用意する。(初めにＡｉ（i=1~N)を入れておく。）

各ｊに対して、vectorにＢｊ枚、Ｃｊを入れる。

vectorをsortする。

大きい方からＮ枚とる。

このＮ枚は明らかに最大値をとり、このようなＮ枚は明らかに構成できる。

・問題点

最大でpush_backをＢ＿ＭＡＸ＊Ｍ＝１０＾１０回することになる。

間に合わない。

解決策

・バケットソートをmapですることにする。

・普通の配列ですると、ＭＬＥする。

実装

#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main() {
  int N, M;
  cin >> N >> M;
  map<int, int> mp;
  for (int i = 0; i < N; i++) {
    int a;
    cin >> a;
    mp[-a]++;
  }

  for (int i = 0; i < M; i++) {
    int b, c;
    cin >> b >> c;
    mp[-c] += b;
  }

  int ans = 0, cont = 0;
  for (auto x : mp) {

    if (cont + x.second >= N) {
      ans += (N - cont) * x.first * -1;
      break;
    }

    ans += x.second * x.first * -1;
    cont += x.second;
  }

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

注意点：

カードの整数値にー１を掛けて大きい方から取り出しています。

（mapで範囲forをすると小さい方から取り出されるため。）

感想：

少し雑な解説になってしまいました。すみません。

感想としては、もう少し早く解けたかなと言う感じです。