POJ 3802 - Cubist Artwork

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

概要

立方体を集めた立体の，正面から見たときの高さの様子と横から見たときの高さの様子が与えられる． 立方体は横方向に w 個，奥方向に d 個ある．

これら2つの図が正しくなるような立体のうち，立方体の数が最小であるようなものを答える．

制約

解法

正面方向と横方向のそれぞれに関して，高さをソートしても答えは変わらない．

降順にソートし，左上のマスからなるべく高いところから順に右下へ行きながら埋めていけばいい (うまく説明できない…)．

例えば 個目のサンプルの場合，

 |4 4 2 2
---------
4|4 4
2|    2 2
1|      1

このように埋めるのが最適．

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8   int W, D;
 9   while (cin >> W >> D && W != 0) {
10     vector<int> ws(W), ds(D);
11     for (int i = 0; i < W; i++) {
12       cin >> ws[i];
13     }
14     for (int i = 0; i < D; i++) {
15       cin >> ds[i];
16     }
17     sort(ws.rbegin(), ws.rend());
18     sort(ds.rbegin(), ds.rend());
19 
20     int ans = 0;
21     int i = 0, j = 0;
22     while (true) {
23       ans += min(ws[i], ds[j]);
24       if (i == W-1 && j == D-1) {
25         break;
26       } else if (i == W-1) {
27         j++;
28       } else if (j == D-1) {
29         i++;
30       } else if (ws[i+1] > ds[j+1]) {
31         i++;
32       } else if (ws[i+1] < ds[j+1]) {
33         j++;
34       } else if (ws[i+1] == ds[j+1]) {
35         i++;
36         j++;
37       }
38     }
39     cout << ans << endl;
40   }
41   return 0;
42 }
poj/3802.cc