POJ 3399 - Product

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

概要

N 個の整数が与えられる． この中から積が最大になるような K 個の数字を出力する．

積を最大にするような K 個の選び方が複数ある場合は，どれを出力しても構わない．

制約

解法

まず例外ケースとして，非負整数が1つも無く K が奇数の場合，どのように選んでも積は負になる． よって，このときは大きい方から K 個選んだときに積が最大になる．

そうでない場合は，うまく K 個選べば積を非負にすることができる．

まず入力を非負と負に分け，それぞれ絶対値に関して大きい順にソートしておく．

K が偶数のとき，非負の上2つの積と負の上2つの積を比べ，大きい方から2つずつ貪欲に選んでいけば最適になる．

一方 K が奇数のときは，必ず1つは非負整数を選ばないと積が非負にならないので，最大の非負整数を最初に選んでから，K-1 で上の手順をすればよい．

 1 #include <iostream>
 2 #include <vector>
 3 #include <deque>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 int main()
 8 {
 9   int N, K;
10   cin >> N >> K;
11   deque<int> pos, neg;
12   for (int i = 0; i < N; i++) {
13     int x;
14     cin >> x;
15     if (x >= 0) {
16       pos.push_back(x);
17     } else {
18       neg.push_back(-x);
19     }
20   }
21   if (K % 2 == 1 && pos.empty()) {
22     sort(neg.begin(), neg.end());
23     for (int i = 0; i < K; i++) {
24       if (i != 0) {
25         cout << " ";
26       }
27       cout << -neg[i];
28     }
29     cout << endl;
30     return 0;
31   }
32 
33   sort(pos.rbegin(), pos.rend());
34   sort(neg.rbegin(), neg.rend());
35 
36   vector<int> ans;
37   if (K % 2 == 1) {
38     ans.push_back(pos[0]);
39     pos.pop_front();
40     K--;
41   }
42   for (; K > 0; K -= 2) {
43     if (pos.size() < 2) {
44       ans.push_back(-neg[0]);
45       ans.push_back(-neg[1]);
46       neg.pop_front();
47       neg.pop_front();
48     } else if (neg.size() < 2) {
49       ans.push_back(pos[0]);
50       ans.push_back(pos[1]);
51       pos.pop_front();
52       pos.pop_front();
53     } else {
54       const int p = pos[0] * pos[1];
55       const int n = neg[0] * neg[1];
56       if (p >= n) {
57         ans.push_back(pos[0]);
58         ans.push_back(pos[1]);
59         pos.pop_front();
60         pos.pop_front();
61       } else {
62         ans.push_back(-neg[0]);
63         ans.push_back(-neg[1]);
64         neg.pop_front();
65         neg.pop_front();
66       }
67     }
68   }
69 
70   sort(ans.rbegin(), ans.rend());
71   for (vector<int>::const_iterator it = ans.begin(); it != ans.end(); ++it) {
72     if (it != ans.begin()) {
73       cout << " ";
74     }
75     cout << *it;
76   }
77   cout << endl;
78   return 0;
79 }
poj/3399.cc