問(wèn)題 1936: [藍(lán)橋杯][算法提高VIP]最大乘積

題目描述

對(duì)于n個(gè)數(shù)，從中取出m個(gè)數(shù)，如何取使得這m個(gè)數(shù)的乘積最大呢？

輸入

第一行一個(gè)數(shù)表示數(shù)據(jù)組數(shù)
每組輸入數(shù)據(jù)共2行：
第1行給出總共的數(shù)字的個(gè)數(shù)n和要取的數(shù)的個(gè)數(shù)m，1<=n<=m<=15，
第2行依次給出這n個(gè)數(shù)，其中每個(gè)數(shù)字的范圍滿(mǎn)足:a[i]的絕對(duì)值小于等于4。

輸出

每組數(shù)據(jù)輸出1行，為最大的乘積。

樣例輸入

1
5 5
1 2 3 4 2

樣例輸出

48

地址

https://www.dotcpp.com/oj/problem1936.html

標(biāo)簽

貪心
分析

因?yàn)閍[i]有正數(shù)也有負(fù)數(shù)，負(fù)負(fù)得正，所以要先把數(shù)列排序，分開(kāi)正負(fù)，分別兩兩相乘進(jìn)行比較。

負(fù)數(shù)兩兩相乘，正數(shù)就單個(gè)相乘。

當(dāng)有多個(gè)數(shù)字，要選擇少量的數(shù)字的時(shí)候，不用擔(dān)心，因?yàn)橐呀?jīng)排好序了，經(jīng)過(guò)判斷會(huì)直接選擇，后面最大的數(shù)字。

package 貪心;

import java.util.Arrays;
import java.util.Scanner;

/**
 * Created with IntelliJ IDEA.
 * User: 76147
 * Date: 2020-02-02
 * Time: 9:57
 * Description: 貪心
 * 地址：https://www.dotcpp.com/oj/problem1936.html
 */
public class 最大乘積 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int a = sc.nextInt();
        for (int i = 0; i < a; i++) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            int arr[] = new int[n];
            for (int j = 0; j < n; j++) {
                arr[j] = sc.nextInt();
            }
            Arrays.sort(arr);
            long res = 1;
            int p = 0, q = n - 1;
            while (m > 0) {
                if (p < n - 1 && q > 0 && (arr[p] * arr[p + 1] > arr[q] * arr[q - 1]) && m >= 2) {
                    res *= (arr[p] * arr[p + 1]);
                    p += 2;
                    m -= 2;
                } else {
                    res *= arr[q];
                    q--;
                    m--;
                }
            }
            System.out.println(res);
        }

    }

}