Official

D - パソコンの販売 / Selling Computers Editorial by physics0523 Editorial for printing


人 \(i\) に売ることができるパソコンは、性能が \(C_i\) 以上であるようなものです。

そこで、問題を以下のように変換します。

  • 以下の要素を含む長さ \(N+M\) の列を降順にソートする。
    • パソコン \((A_i,B_i)\)
    • 人 \((C_i,-1)\)

すると、人 \(i\) に売ることができるのはその人以前に出てきたパソコンに限られます。

このとき、以下の貪欲法が成り立ちます。

  • 人が出てくるたびに、すでに出てきたパソコンのうち最も高額なパソコンをその人に売ることにする。ただし、もう売れるパソコンがない場合は答えは -1 である。

略証: 人 \(i\) に対して最も高額なパソコンをスキップした場合を考える。そのパソコンが最後まで売れない場合、人 \(i\) にそのパソコンを売りつけたことにして損しない。そのパソコンが後から人 \(j\) に売れた場合、 人 \(i,j\) に売ったパソコンを入れ替えて人 \(i\) に最も高額なパソコンを売りつけたことにして損しない。

その時点で最も高額なパソコンは、 priority_queue などの「最大値を取り出す」ことができるデータ構造を用いることで検出できます。

本解法の時間計算量は \(O((N+M) \log (N+M))\) です。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using ll=long long;
using pl=pair<ll,ll>;

int main(){
  ll N,M;
  cin >> N >> M;
  vector<pl> event;
  for(ll i=0;i<N;i++){
    ll A,B;
    cin >> A >> B;
    event.push_back({A,B});
  }
  for(ll i=0;i<M;i++){
    ll C;
    cin >> C;
    event.push_back({C,-1});
  }
  sort(event.rbegin(),event.rend());

  ll res=0;
  priority_queue<ll> pq;
  for(auto &nx : event){
    if(nx.second==-1){
      if(pq.empty()){cout << "-1\n"; return 0;}
      res+=pq.top(); pq.pop();
    }
    else{
      pq.push(nx.second);
    }
  }
  cout << res << "\n";
  return 0;
}

posted:
last update: