[AtCoder] ABC 137 D – Summer Vacation

2019年8月11日2019年8月24日

問題

方針

「明日できることは今日するな」ということで、締め切りから考えていきます。残り \( i \) 日あるとき、まだ請け負っていないアルバイトに対して \( A_j \leq i \) を満たすものの中で報酬が一番大きいものを選びます。これを \( i = 1 \) から \( i = M \) まで調べていきます。したがって、 \( A_j \) を昇順に整列させ、\( A_j \leq i \) を満たすアルバイトについて、優先度付きキューに \( B_j \) を格納します。そして、キューに値が存在すれば、最大の報酬を一つ加算していきます。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct Data {
  int A, B;
  Data(int A, int B) : A(A), B(B){}
  bool operator< (const Data& d) const {
    return A < d.A;
  } 
};

int main() {
  int N, M;
  cin >> N >> M;
  priority_queue<int> q;
  int A, B;
  vector<Data> d;
  for (int i = 0; i < N; i++) {
    cin >> A >> B;
    d.push_back(Data(A, B));
  }
  sort(d.begin(), d.end());
  int c = 0;
  int idx = 0;
  for (int i = 1; i <= M; i++) {
    while (idx < N && d[idx].A <= i) {
      q.push(d[idx].B);
      idx++;
    }
    if (!q.empty()) {
      c += q.top();
      q.pop();
    }
  }
  cout << c << "\n";
  return 0;
}