my image ...

【AtCoder】ABC127 D - Integer Cards

公開: 2023/07/24

YouTubeの解説を見てやっと理解してACできたためそのメモ。簡単にいうと、数を書き換えて輪を最大にする問題。
https://atcoder.jp/contests/abc127/tasks/abc127_dhttps://atcoder.jp/contests/abc127/tasks/abc127_d

N枚のカードと値がCjのBj枚のカード×M枚をソートして大きい順からN枚選んで合計すれば良いが、それだとTLEになってしまう。

priority_queueとpairを使用して何(数値)が何枚あるかという情報をpriority_queueに入れてN回ループで取り出した数を合計するアルゴリズムを組んだ。

解答

#include<bits/stdc++.h>
using namespace std;
#define rep(i, N) for (int i = 0; i < N; ++i)

int main () {
  long long N,M;
  cin >> N >> M;
  vector<long long> A(N);
  vector<long long> B(M);
  vector<long long> C(M);
  priority_queue< pair<long long, long long> > q;
  rep(i, N) cin >> A[i];
  rep(i, M) cin >> B[i] >> C[i];
  rep(i, N) q.push(make_pair(A[i], 1));
  rep(i, M) q.push(make_pair(C[i], B[i]));

  long long ans = 0;
  rep(i, N) {
    auto P = q.top();
    q.pop();
    ans += P.first;
    if (P.second > 1) {
      P.second--;
      q.push(P);
    }
  }
  cout << ans << endl;
}
©️ 2023 takumi