题解：最大乘积K元素选择问题

题目分析

给定一个包含N个整数的数组，需要从中选择K个元素，使得它们的乘积最大。输出这K个元素，并按非递增顺序排列。关键在于处理各种情况，包括正数、负数和零的组合，以确保乘积最大化。

解题思路

该题的核心思路是贪心策略：通过合理选择正数和负数的组合，使得乘积最大化。具体步骤如下：

1. 数据预处理：将数组分为非负数（numz）和负数（numf）两部分，并分别排序。

   • 非负数按升序排列（便于取最大的数）。
   • 负数按升序排列（便于取绝对值最大的负数）。

2. 处理K为奇数的情况：

   • 如果有非负数，优先选择最大的非负数（因为奇数个元素的乘积符号由正数决定）。
   • 如果没有非负数（全为负数），则只能选择绝对值最小的K个负数。

3. 处理K为偶数的情况：

   • 每次选择两个数，比较以下两种组合的乘积：
     • 两个最大的非负数（如果有至少两个）。
     • 两个最小的负数（即绝对值最大的负数，乘积为正）。
   • 选择乘积较大的组合，直到选满K个元素。

4. 输出结果：将选择的元素按非递增顺序排序后输出。

代码实现分析

#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;
#define MAXN 117

int main()
{
    int n, k;
    int a[MAXN], numz[MAXN], numf[MAXN]; // 原数组、非负数数组、负数数组
    int ans[MAXN]; // 存储最终选择的元素
    int i, j;
    int num1, num2; // 非负数和负数的数量
    
    while(~scanf("%d %d",&n,&k))
    {
        num1 = num2 = 0;
        // 分离非负数和负数
        for(i = 0; i < n; i++)
        {
            scanf("%d",&a[i]);
            if(a[i] >= 0)
                numz[num1++] = a[i]; // 非负数
            else
                numf[num2++] = a[i]; // 负数
        }
        
        // 分别排序
        sort(numz,numz+num1); // 非负数升序
        sort(numf,numf+num2); // 负数升序（绝对值降序）
        
        int cont = 0; // 记录答案数组的长度
        
        // 处理K为奇数的情况
        if(k&1)
        {
            k--; // 减少一个元素，转为偶数处理
            if(num1 > 0)
                ans[cont++] = numz[--num1]; // 选择最大的非负数
            else // 没有非负数，全为负数
            {
                for(i = num2-1; i > num2-k-1; i--)
                {
                    printf("%d ",numf[i]);
                }
                printf("%d\n",numf[num2-k-1]);
                continue;
            }
        }
        
        j = 0; // 负数数组的指针
        // 每次选择两个元素，直到选满K个
        for(i = 0; i < k/2; i++)
        {
            int t1 = -4017; // 初始化两个乘积为极小值
            int t2 = -4017;
            
            // 处理剩余元素不足的边界情况
            if(num1 == 1 && num2-j == 1)
            {
                ans[cont++] = numz[--num1];
                ans[cont++] = numf[++j];
            }
            else
            {
                // 计算两种选择的乘积
                if(num1 > 1)
                    t1 = numz[num1-1]*numz[num1-2]; // 两个最大的非负数
                if(num2-j > 1)
                    t2 = numf[j] * numf[j+1]; // 两个最小的负数（绝对值最大）
                
                // 选择乘积较大的组合
                if(t1 > t2)
                {
                    ans[cont++] = numz[--num1];
                    ans[cont++] = numz[--num1];
                }
                else
                {
                    ans[cont++] = numf[j++];
                    ans[cont++] = numf[j++];
                }
            }
        }
        
        // 排序并输出结果
        sort(ans,ans+cont);
        for(i = cont-1; i > 0; i--)
        {
            printf("%d ",ans[i]);
        }
        printf("%d\n",ans[0]);
    }
    return 0;
}

关键细节说明

1. 边界条件处理：

   • 当K为奇数且没有非负数时，直接输出绝对值最小的K个负数。
   • 在每次选择两个元素时，考虑剩余元素不足的情况（如代码中的num1 == 1 && num2-j == 1）。

2. 贪心策略：

   • 通过比较两种组合的乘积，确保每次选择都能使乘积最大化。
   • 优先选择正数可以避免负数的乘积符号问题，特别是在K为奇数时。

3. 时间复杂度：

   • 排序操作：O(N log N)
   • 选择元素：O(K)
   • 总体复杂度：O(N log N + K)，适用于题目给定的数据范围（N ≤ 100）。