ABC137 D問題 Summer Vacation

atcoder.jp

 

問題文

$N$ 件の日雇いアルバイトがあり、$i$ 件目の日雇いアルバイトを請けて働くと、その $A_i$ 日後に報酬 $B_i$ が得られます。

あなたは、これらの中から $1$ 日に $1$ 件まで選んで請け、働くことができます。

ただし、請けたことのある日雇いアルバイトは選べません。

今日から $M$ 日後まで($M$ 日後を含む)に得られる報酬の合計の最大値を求めてください。

なお、日雇いアルバイトは今日から請けて働くことができます。

制約

• 入力は全て整数である。
• $1\le N\le {10}^5$
• $1\le M\le {10}^5$
• $1\le A_i\le {10}^5$
• $1\le B_i\le {10}^4$

解法の方針

1. 最終日から数えていき、できるようになった仕事を集合に追加する
2. 集合にはprioriuty_queueを用いる

注意点

• 最終日から遡る必要がある

　　　貪欲法を用いるには単純比較可能である必要があり、賃金要素だけにしたいため

解答例

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

int main(){
  int n,m;
  cin>>n>>m;
  vector<vector<int>> jobs(m);   //何日目に解禁される仕事かを保持するvector
  rep(i,n){
    int a,b;
    cin>>a>>b;
    if(a>m) continue;
    jobs[m-a].push_back(b);   //m-a日目に解禁される要素として追加　比較はbでするのでbだけ追加
  }
  priority_queue<int> q;
  ll ans=0;
  for(int i=m-1;i>=0;--i){
//m-1日目から遡ってvectorの要素をpriority_queueに移す
    for(int b : jobs[i]){
      q.push(b);
    }
    if(!q.empty()){   //空でtop()すると壊れる
      ans += q.top();   //ansに収入を足す
      q.pop();   //やった仕事は消す
    }
  }
  cout<<ans<<endl;
}

学んだこと

• 逆順に見ていく

　　　今回の問題では、日数がたつにつれてできる仕事が減っていく

　　　そのため、最終日から遡っていくことで、賃金だけで比較できるようになり、次の貪欲法が使えるようになる

　　　だんだん絞られていくような問題では、後ろからゴールから考えるという手法も覚えておきたい

• 貪欲法

　　　一番いいものを順番に選んでいくやり方

　　　何をもって「一番いい」か決めるために、比較要素を一つに絞る必要がある

　　　次に書くpriority_queueとも関わりがある

• priority_queue

 　　　.push()で要素を追加し、.top()で取り出すと、大きいものから順に出てくるコンテナ

　　　知らなかったのでいちいちソートするのか？と思っていたが、これを使うとO(logN)でできるらしい