蓝桥杯[省赛][B组]-乘积最大

题目来自蓝桥杯练习系统

这一题存在一个组合C(k,n),选择的就是组合中的其中一个，如果一个条件一个条件的考虑的话非常麻烦，比赛时也会浪费大量时间，实在想不出思路的话可以去暴力拿一些分

#include
#include

升序排序，然后运用algorithm库中的next_permutation函数去获得下一个全排列，每次得到前k个再累乘，就可以拿到40分（思考一下怎么剪枝也许可以拿更多分）

这40分几乎是一半了，而且是毫无疑问能拿到的，如果时间不够充沛可以这样骗一波分，总比没有好。

当然，想要更多的分还是必须去思考如何求解的。

这里笔者去认真学习了一番：https://blog.csdn.net/weixin_52797843/article/details/122371558?spm=1001.2101.3001.6650.6&utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7ERate-6.pc_relevant_default&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7ERate-6.pc_relevant_default&utm_relevant_index=12

#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int N = 100010, mod = 1000000009;
int n, k;
int a[N];
int main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>k;
    for(int i=0; i>a[i];
    sort(a,a+n);
    int res=1;
    int l=0,r=n-1;//左右下标
    int sign=1;
    if(k%2) { //如果k是奇数，先把奇数转化为偶数
//    这边res取得是最大值，一般是正数(通常情况下最大值一定要取) 
        res=a[r--];
        k--;
//        如果res小于0，就说明全是负数，这个时候颠倒判断符号取最大值（如果是奇数又全为负数必然结果是负数） 
        if(res<0) sign=-1;
    }
    //k是偶数，每次从左选两个，从右选两个，比较大小
    while(k) {
        LL x=(LL)a[l]*a[l+1],y=(LL)a[r-1]*a[r];
//        如果k原本就是偶数 
        if(x*sign>y*sign) {
            res=x%mod*res%mod;
            l+=2;
        } else {
            res=y%mod*res%mod;
            r-=2;
        }
        k-=2;
    }
    cout<<res;
    return 0;
}