蟻本の練習問題埋め2-4(1)

蟻本

プライオリティーキュー

POJ 3614 - Sunscreen

http://poj.org/problem?id=3614

問題

C引きの牛に日焼け止め（SPF）を塗る。
牛iに塗れるSPFの強さは限られていて、下限minSPF[i]と上限maxSPF[i]が与えられる。
SPFはL種類あり、j種類目のSPFは、強さSPF[j]で最大cover[j]匹の牛を塗ることが出来る。
このとき、SPFを塗れる牛の数の最大値を求めよ。

制約

C,L<=2500
minSPF[i],maxSPF[i]<=1000

解法

まず最大流が思いつくが、計算量的に厳しい（しかしDinicで通るらしい）。
そこで貪欲で解く。
SPF[j]が小さい順に使っていく。
このとき、まだ残ってる牛のうち、
minSPF[i] <= SPF[j] <= maxSPF[i]
を満たす牛の中で、maxSPF[i]が最も小さいものにj種類目のSPFを使っていく。
この貪欲が上手く行く理由は、この条件を満たす牛を使わないことによって得をすることはないから。
実際には、minSPF[i]で牛をソートし、SPF[j]でSPFをソートする。
さらに、minSPF[i] <= SPF[j]を満たす牛をプライオリティーキューに入れる。
このプライオリティーキューはmaxSPF[i]が小さい順にとり出されるようにする。
詳しくはソース参照。

ソース
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)n;++i)
typedef pair<int,int> pii;

struct Cmp {
  bool operator()(const pii &a, const pii &b) {
    return a.second > b.second;
  }
};

pii cow[2500];
pii spf[2500];

int main() {
  int C,L;
  scanf("%d %d", &C, &L);
  REP(i,C) {
    scanf("%d %d", &cow[i].first, &cow[i].second);
  }
  REP(i,L) {
    scanf("%d %d", &spf[i].first, &spf[i].second);
  }
  sort(cow,cow+C);
  sort(spf,spf+L);
  priority_queue<pii,vector<pii>,Cmp> Q;
  int i=0,j=0;
  int ans = 0;
  while(j<L) {
    while(i<C) {
      if (cow[i].first <= spf[j].first) {
        Q.push(cow[i]);
        i++;
      } else break;
    }
    if (Q.empty()) j++;
    while(Q.size()) {
      pii now = Q.top(); Q.pop();
      if (now.second<spf[j].first) continue;
      spf[j].second--;
      ans++;
      if (spf[j].second == 0) j++;
      break;
    }
  }
  printf("%d\n", ans);
}

POJ 2010 - Moo University - Financial Aid

http://poj.org/problem?id=2010

問題

C匹の牛が大学の受験をし、N匹の牛の入学を許可する。
各牛について、テストのスコアと必要な補助金の情報が与えられる。
大学として出せる補助金の最大値Fが決まっているので、補助金の合計がFを超えないように、出来るだけ優秀な牛を入学させたい。
ここでは、N匹の牛のスコアの中央値を最大化することを考える。
最適なN匹を選んだときのスコアの中央値の最大値を求めよ。
N匹を選べなければ-1。

制約

N<=19999
N<=C<=10^5
Nは奇数
F<=2*10^9
スコア<=2*10^9

解法

中央値の候補を全部試して、それぞれFを超えないように牛を選ぶことが出来るかをO(1)で調べれば解ける。
まずスコアでソートする。
i番目の牛のスコアを中央値とすることを考える。
この時、1 〜 i-1番目の牛からN/2匹、 i+1 〜 C番目の牛からN/2匹を選ぶことになる。
よって
lower[i] = 1 〜 i-1番目の牛からN/2匹選ぶときに必要な補助金の最小値
upper[i] = i+1 〜 C番目の牛から　　　〃
という２つのテーブルを作れば、上手く処理することが出来る。
プライオリティーキューを使うと上手くテーブルを作ることが出来る。
必要な補助金が大きい牛から選ばないことにするというイメージ。