[UVA][greedy] 10747 - Maximum Subsequence
Problem H
Maximum Subsequence
Input: Standard Input
Output: Standard Output
Time Limit: 2 Second
You are given a sequence of N integers, each of which is not greater than 10,000 considering absolute value. There are (NCK) sub-sequences possible from this sequence. You have to pick such a subsequence, so that multiplication of all its integers is maximum.
For example, if the sequence is 4, 4, -4, -4 and you are asked to pick 2 integers. You have 2 ways, which will satisfy the criterion. One is to pick 4,4 and the other is to pick –4, -4.
In this case, you have to consider the sub sequence whose summation of all integers is maximum.
Input
The input file contains several sets of inputs. The description of each set is given below.
Each input set starts with 2 positive integers N, K (1<=K<=N<=10000). Next N non-empty lines contain N integers in total.
Input is terminated by a case where N=0 and K=0. This case should not be processed. There will be at most 60 test cases.
Output
For each set of input print in a single line the summation of the integers in the desired subsequence.
Sample Input Output for Sample Input
|
4 4 1 2 3 4 4 1 1 2 3 4 4 2 44–4–40 0 |
10 4 8 |
Problem setter: Md. Kamruzzaman, EPS
Special Thanks: Monirul Hasan, EPS
題目描述：
從 N 個數字中挑 K 個數字相乘，在乘積最大的情況下，總和最大為多少。
題目解法：
考慮乘積 > 0 < 0 = 0
先按照絕對值排大小(小->大)，再對正負排序(正->負)
1) = 0 不用說，先將所有最大正數依序挑起，不夠的挑負數，而既然會 = 0，必然會挑到 0
2) < 0 由於判斷不管怎麼樣乘積肯定會小於 0，則挑前面 K 個數字即可。
3) > 0 比較麻煩。
這 1)2)3) 的判斷是要看正正跟負負的對數可以不以湊成 K/2 對，
但是如果 K 是奇數，則要先挑出一個正數，在去看對數。
接著考慮 3) > 0
如果 K 是奇數，先從正數群中挑一個最大的數字出來。
接著只要考慮 K 是偶數，每次挑兩個最大正數，跟兩個最大(絕對值)負數。
如果兩個正的乘積大於等於負數，則先挑正的那一方，反之負數。
#include <string.h>
#include <algorithm>
using namespace std;
bool cmp(int a, int b) {
if(abs(a) != abs(b))
return abs(a) < abs(b);
return a < b;
}
int N, K, A[10005];
void sol1() {
int ret = 0;
int pf = 0, pa, pb, pidx = N-1;
int nf = 0, na, nb, nidx = N-1;
int used[10005] = {};
if(K%2 == 1) {
while(A[pidx] < 0) pidx--;
ret += A[pidx];
pidx--;
K--;
}
while(K) {
while(pf < 2 && pidx >= 0) {
if(A[pidx] > 0) {
if(pf == 0) pa = A[pidx];
if(pf == 1) pb = A[pidx];
pf++;
used[pidx] = 1;
}
pidx--;
}
while(nf < 2 && nidx >= 0) {
if(A[nidx] < 0) {
if(nf == 0) na = A[nidx];
if(nf == 1) nb = A[nidx];
nf++;
}
nidx--;
}
if(pf != 2 && nf == 2) {
ret += na+nb;
nf = 0;
} else if(pf == 2 && nf != 2) {
ret += pa+pb;
pf = 0;
} else {
if(na*nb > pa*pb) {
ret += na+nb;
nf = 0;
} else {
ret += pa+pb;
pf = 0;
}
}
K -= 2;
}
printf("%d\n", ret);
}
void sol2() {
int ret = 0, i;
for(i = 0; i < K; i++)
ret += A[i];
printf("%d\n", ret);
}
void sol3() {
int ret = 0, i;
for(i = N-1; i >= 0 && K; i--)
if(A[i] >= 0)
ret += A[i], K--;
for(i = 0; i < N && K; i++)
if(A[i] < 0)
ret += A[i], K--;
printf("%d\n", ret);
}
int main() {
int i;
while(scanf("%d %d", &N, &K) == 2 && N) {
for(i = 0; i < N; i++)
scanf("%d", &A[i]);
sort(A, A+N, cmp);
// maybe multiplication > 0 ?
int pos = 0, neg = 0;// zero not in pos or neg
for(i = 0; i < N; i++) {
if(A[i] > 0) pos++;
if(A[i] < 0) neg++;
}
if(K%2 == 0 && pos/2 + neg/2 >= K/2) {
sol1();
} else if(K%2 == 1 && (pos+1)/2 + neg/2 > K/2 && pos > 0) {
sol1();
}
else {
if(A[0] == 0)
sol3();
else
sol2();
}
}
return 0;
}