「スタッフ \(i\) が仕事 \(j\) を割り当てられるのは \(D_j/V_i \le T_j\) を満たす場合に限られる」とありますが、この条件を整理してみましょう。

添え字 ( \(V_i\) の \(i\) 、 \(D_j\) の \(j\) など ) が同じものを同じ側に持って行くように変形するとよい見通しが立つことがあります。

この問題の制約下で、 \(D_j / V_i \le T_j \Leftrightarrow D_j \le T_j \times V_i \Leftrightarrow D_j/T_j \le V_i\) と同値変形できます。

このことから、 \(D_j/T_j\) が小さい仕事から順にこなしていって損しないことが分かります。
理由: そうなっていない時に割り当てる仕事を \(D_j/T_j\) が小さいものに適切にシフトすることで、依然同じ件数の実行可能な割り当てを得ることができます。

また、割り当てる仕事を \(D_j/T_j\) の昇順に並べた時、スタッフもまた \(V_i\) の昇順に割り当てられているとして損しません。
理由: これに違反する ( \(D_j/T_j\) の大きい仕事に \(V_i\) の小さいスタッフが割り当てられている ) 状況があった場合、 \(D_j/T_j\) の大小関係に従うようにスタッフを入れ替えることで依然同じ件数の実行可能な割り当てを得ることができます。

よって、以下の貪欲法が成り立ちます。

• まず、仕事を \(D_j/T_j\) の昇順にソートする。
• 次に、スタッフを \(V_i\) の昇順にソートする。
• 仕事の列の先頭である仕事 \(j\) とスタッフの列の先頭である仕事 \(i\) とで、 \(D_j/T_j\) と \(V_i\) を比較する。
  • もし \(D_j/T_j \le V_i\) であれば、仕事とスタッフをマッチングさせて問題ありません。両者を列から削除します。
  • もし \(D_j/T_j > V_i\) であれば、スタッフ \(i\) ができる仕事はもうないので、スタッフのみ列から削除します。

本解法はソートがボトルネックで、時間計算量 \(O(N \log N + M \log M)\) で動作します。

なお、分母・分子が共に正整数である分数 \(p/q,r/s\) の大小関係は \(ps,qr\) の大小関係に一致することを利用することで数値誤差による不正解を回避することができます。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

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

int compare(pl x,pl y){
  ll v=x.first*y.second-x.second*y.first;
  if(v>0){return 1;}
  else if(v<0){return -1;}
  return 0;
}

bool comp(const pl &l,const pl &r){
  return (compare(l,r)==-1);
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll n,m;
  cin >> n >> m;
  vector<pl> v(n);
  for(auto &nx : v){
    cin >> nx.first;
    nx.second=1;
  }
  vector<pl> w(m);
  for(auto &nx : w){
    cin >> nx.first >> nx.second;
  }

  sort(v.begin(),v.end(),comp);
  sort(w.begin(),w.end(),comp);
  ll p=0,q=0,res=0;
  while(p<n && q<m){
    if(compare(v[p],w[q])>=0){p++; q++; res++;}
    else{p++;}
  }
  cout << res << "\n";
  return 0;
}