POJ 3497 - Assemble

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

概要

n 個のパーツがあり，それぞれに

• 種類
• 名前
• 値段
• 品質

が設定されている．

すべての種類のパーツを1つずつ買ったときの，品質の最小値を最大化したい．

ただし，値段の合計は b 以下になるように買わなければならない．

制約

• 1 <= n <= 1000
• 1 <= b <= 1000000000
• 0 <= price <= 1000000
• 0 <= quality <= 1000000000
• 種類と名前は20文字以下のアルファベットと数字とアンダースコアからなる文字列

解法

品質の最小値 Q に関して二分探索．

各種類のパーツの中で，品質が Q 以上で値段が最小のものを買ったときの値段の合計が b 以下であれば，その Q を達成できる．

 1 #include <cstdio>
 2 #include <string>
 3 #include <vector>
 4 #include <map>
 5 using namespace std;
 6 
 7 bool ok(const map<string, vector<pair<int,long long> > >& m, long long B, long long Q)
 8 {
 9   long long b = 0LL;
10   for (map<string, vector<pair<int,long long> > >::const_iterator it = m.begin(); it != m.end(); ++it) {
11     const vector<pair<int,long long> >& v = it->second;
12     static const long long INF = 1LL<<60;
13     long long x = INF;
14     for (vector<pair<int,long long> >::const_iterator jt = v.begin(); jt != v.end(); ++jt) {
15       if (jt->second >= Q) {
16         x = min(x, static_cast<long long>(jt->first));
17       }
18     }
19     if (b == INF) {
20       return false;
21     }
22     b += x;
23     if (b > B) {
24       return false;
25     }
26   }
27   return b <= B;
28 }
29 
30 int main()
31 {
32   int T;
33   scanf("%d", &T);
34   while (T-- > 0) {
35     int N;
36     long long B;
37     scanf("%d %lld", &N, &B);
38     map<string, vector<pair<int,long long> > > m;
39     for (int i = 0; i < N; i++) {
40       char type[30], name[30];
41       int price;
42       long long quality;
43       scanf("%s %s %d %lld", type, name, &price, &quality);
44       m[type].push_back(make_pair(price, quality));
45     }
46 
47     long long left = 0LL, right = 1000000000LL;
48     while (left < right) {
49       const long long mid = (left + right)/2LL;
50       if (ok(m, B, mid)) {
51         left = mid+1;
52       } else {
53         right = mid;
54       }
55     }
56     printf("%lld\n", left-1LL);
57   }
58   return 0;
59 }