AtCoder Beginner Contest 137 D – Summer Vacationの解法

問題はこちら

制約の中で最大値を求める問題のため、貪欲法が適用できそうだとアタリを付けます。実行可能な日雇いアルバイトの中で、最大値を常に選択すれば、最大値になりそうです。が、１日目から順に実行可能な最大報酬の日雇いアルバイトを選んで行くと、数日後に次点で最大報酬だが実行不可能なアルバイトが出てきた場合に最適解とはなりません。例えば、二日間の最大報酬を求める場合に、2日後に１万円、１日後に２万円もらえる日雇いアルバイトがそれぞれある場合、最大値として１日目に２万円のアルバイトを受けてしまうと、二日目に実行可能なアルバイトがなくなるため最適解ではないです。

上の例で問題なのは実行可能であったはずなのに実行不可能なアルバイトが途中で出てしまうことです。これは、１日目から選んでいくのではなく、最終日から選んでいくことで解決できます。最終日から選ぶことで、実行不可能な日雇いアルバイトが出ることはありません。むしろ、日にちを戻るにつれて、実行可能な日雇いアルバイトが増えていくことになります。以上を最善手として、コードにすれば良いです。以下、解法です。

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    int N, M; cin >> N >> M;
    vector<int> v[100001];
    for (int i=0; i<N; i++) {
        int A, B; cin >> A >> B;
      	v[A].push_back(B);
    }
  
    int ans = 0;
    priority_queue<int> pq;
    for (int i=1; i<=M; i++)
    {
        for (auto e : v[i]) pq.push(e);
   	if (! pq.empty()) {
          ans += pq.top();
          pq.pop();
        }
    }
 
    cout << ans << endl;
}