POJ 1456 - Supermarket

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

概要

n 個の商品があり，i 番目の商品は時刻 d[i] までなら売ることで p[i] の利益を得ることができる． 時刻 1 からスタートし，1つの商品を売るのには単位時間掛かる．

このとき，得られる利益の合計の最大値を答える．

制約

• 0 <= n <= 10^4
• 1 <= p[i] <= 10^4
• 1 <= d[i] <= 10^4

解法

• d[i] >= 10000 の商品のうち最も利益が大きい商品
• d[i] >= 9999 の商品のうち最も利益が大きい商品
• ...
• d[i] >= 1 の商品のうち最も利益が大きい商品

と，d の大きい商品から順に貪欲に選んでいけばよい． priority_queue を使うと楽．

n == 0 という入力がくる点に注意．

 1 #include <cstdio>
 2 #include <vector>
 3 #include <queue>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 int main()
 8 {
 9   int N;
10   while (scanf("%d", &N) != EOF) {
11     if (N == 0) {
12       puts("0");
13       continue;
14     }
15     vector<pair<int,int> > v(N);
16     for (int i = 0; i < N; i++) {
17       scanf("%d %d", &v[i].second, &v[i].first);
18     }
19     sort(v.rbegin(), v.rend());
20     long long ans = 0LL;
21     priority_queue<int> q;
22     vector<pair<int,int> >::const_iterator it = v.begin();
23     for (int d = it->first; d > 0; d--) {
24       while (it != v.end() && it->first == d) {
25         q.push(it->second);
26         ++it;
27       }
28       if (!q.empty()) {
29         ans += static_cast<long long>(q.top());
30         q.pop();
31       }
32     }
33     printf("%lld\n", ans);
34   }
35   return 0;
36 }