POJ 2220 - Treasure Hunters

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

概要

\(t\) 個の宝を \(h\) 人のハンターで分け合う。 各宝に対して、各ハンターがいくらの価値があると考えているかが与えられる。 あるハンターが得た利益は、そのハンターに分けられた宝をそのハンターの価値で合計したものとする。 最大の利益を得たハンターと最小の利益を得たハンターの差が最小になるような宝の分け方を答える。

制約

解法

\(h ^ t\) 通り全探索。

 1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   for (string dummy; cin >> dummy;) {
 8     int T, H;
 9     cin >> T >> H;
10     int v[6][8];
11     for (int i = 0; i < H; i++) {
12       for (int j = 0; j < T; j++) {
13         cin >> v[i][j];
14       }
15     }
16     cin >> dummy;
17 
18     unsigned S = 1;
19     for (int i = 0; i < T; i++) {
20       S *= H;
21     }
22     int mind = 10000000;
23     int ans[6][9];
24     for (int i = 0; i < H; i++) {
25       fill_n(ans[i], T+1, 0);
26     }
27     for (unsigned s = 0; s < S; s++) {
28       int w[6][9];
29       int *p[6];
30       for (int i = 0; i < H; i++) {
31         fill_n(w[i], T+1, 0);
32         p[i] = w[i];
33       }
34       int ttl[6];
35       fill_n(ttl, H, 0);
36       unsigned t = s;
37       for (int i = 0; i < T; i++) {
38         *p[t%H] = i+1;
39         ++p[t%H];
40         ttl[t%H] += v[t%H][i];
41         t /= H;
42       }
43       int hi = 0, lo = 10000000;
44       for (int i = 0; i < H; i++) {
45         hi = max(hi, ttl[i]);
46         lo = min(lo, ttl[i]);
47       }
48       int d = hi - lo;
49       if (d < mind) {
50         mind = d;
51         for (int i = 0; i < H; i++) {
52           copy(w[i], w[i]+T, ans[i]);
53         }
54       }
55     }
56     for (int i = 0; i < H; i++) {
57       int a = 0;
58       bool first = true;
59       for (int *p = ans[i]; *p != 0; p++) {
60         if (!first) {
61           cout << " ";
62         }
63         first = false;
64         cout << *p;
65         a += v[i][*p-1];
66       }
67       if (!first) {
68         cout << " ";
69       }
70       cout << a << endl;
71     }
72     cout << endl;
73   }
74   return 0;
75 }
poj/2220.cc