题目描述

给定 N 个整数 A1,A2,…AN。

请你从中选出 K 个数，使其乘积最大。

请你求出最大的乘积，由于乘积可能超出整型范围，你只需输出乘积除以 1000000009 的余数。

注意，如果 X<0， 我们定义 X 除以 1000000009 的余数是负(−X)除以 1000000009 的余数，即：0−((0−x)%1000000009)

输入格式

第一行包含两个整数 N 和 K。

以下 N 行每行一个整数 Ai。

输出格式

输出一个整数，表示答案。

数据范围

$1<=k<=N<=10^5$

$-10^5<=A_i<=10^5$

代码问题:

(1).注意代码逻辑的完整性——sign=-1必须放在k%2中判断
(2).求余后的两个数显然是无法比较大小的
(3).bool sign=-1实际为1(编译器无法检测该错误)

贪心——分类讨论

1.性质分析:
(1).当所有数都为正数时,解必然为正数
(2).当k==n时,ans为直接相乘
2.分类讨论:
(1).当n==k,直接取k个数
(2).k[HTML_REMOVED]0或小于0
当c>0,cb>ab
当c<0,ca>ab
显然这与总是取值较大的方式相矛盾,假设错误,原命题成立
(4).k<n且k为奇数,全为正数,结果必然为正数,每次取较大值
(5).k<n且k为奇数,有正数有负数,结果必然为正数,因为加入先取出一个正数,那么就能将结果转化为(3)
(6).k<n且k为奇数,全为负数,结果必然为负数,先取出一个最小负数,然后每次取最小值即可

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define mod 1000000009

注意:其实这里分类讨论还有一个细节,第一个划分依据应该是k==n,因为k==n比所有数都为正数好判断

using namespace std;
typedef long long ll;

const int N=1e5+10;

ll arr[N];

ll get_mod(ll now)
{
    if(now>=0){
        return now%mod;
    }
    else{
        return 0-(0-now)%mod;
    }
}

int main()
{
    int n,k;
    cin >> n >> k;
    for(int i=1;i<=n;i++){
        scanf("%lld",&arr[i]);
    }

    sort(arr+1,arr+n+1);

    int sign=1;
    ll ans=1;
    if(n==k){
        for(int i=1;i<=n;i++){
            ans=get_mod(ans*arr[i]);
        }
    }
    else{
        //cout << sign << endl;
        if(k%2){
            //如果k是奇数
            ans=arr[n--];
            k--;
            //当k<n且k为奇数且最大值为负数
            if(arr[n]<0){
                sign=-1;
            }
        }
        int l=1,r=n;
        while(k){
            ll front=arr[l]*arr[l+1];
            ll back=arr[r]*arr[r-1];
            //与sign结合起来非常巧妙的同时比较大小的方法
            if(front*sign<=back*sign){
                back=get_mod(back);
                ans=get_mod(ans*back);
                r-=2;
            }
            else{
                front=get_mod(front);
                ans=get_mod(ans*front);
                l+=2;
            }
            k-=2;
            //cout << sign << endl;
        }
    }
    cout << ans << endl;
    return 0;
}