2013-07-23 06:31:09| 人氣691| 回應0 | 上一篇 | 下一篇

[UVA][greedy] 10747 - Maximum Subsequence

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

4 1

4 2

–4

–4

0 0

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 <stdio.h>
#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;
}

我要檢舉

#10747#Maximum Subsequence#greedy

台長： Morris

您可能對以下文章有興趣

[UVA][字串] 126 - The Errant Physicist

[UVA] 10865 - Brownie Points

[UVA] 10945 - Mother bear

[UVA][概率DP] 11762 - Race to 1

人氣(691) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][java] 10992 - The Ghost of Programmers
此分類上一篇:[UVA] 1195 - Calling Extraterrestrial Intelligence Again

回應(0)