凡森Zfans

用户名：Zfans

访问量：34258

签　名：

路漫漫其修远兮，吾将上下而求索。

等　　级
排　　名	157
经　　验	7174
参赛次数	0
文章发表	105
年　　龄	21
在职情况	学生
学　　校	重庆交通大学
专　　业	计算机科学与技术

　　自我简介：

热爱学习的大学生。

TA的其他文章

蓝桥杯算法提高VIP-计算时间-题解(C++代码) by Zfans.
浏览：174

蓝桥杯基础练习VIP-Sine之舞-题解(C++代码) by Zfans.
浏览：744

蓝桥杯算法提高VIP-扫雷-题解(C++代码) by Zfans.
浏览：144

你可能喜欢

蓝桥杯2018年第九届真题-乘积最大-题解（C++代码）

　　作者: 凡森Zfans　　　　发表时间：2020-08-26 15:11:43 浏览：965　|　评论：0　

原题链接：蓝桥杯2018年第九届真题-乘积最大

```cpp
/*乘积最大

给定N个整数A1, A2, ... AN。请你从中选出K个数，使其乘积最大。

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

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

【输入格式】
第一行包含两个整数N和K。
以下N行每行一个整数Ai。

对于40%的数据，1 <= K <= N <= 100
对于60%的数据，1 <= K <= 1000
对于100%的数据，1 <= K <= N <= 100000  -100000 <= Ai <= 100000

【输出格式】
一个整数，表示答案。

【输入样例】
5 3
-100000
-10000
2
100000
10000

【输出样例】
999100009

再例如：
【输入样例】
5 3
-100000
-100000
-2
-100000
-100000

【输出样例】
-999999829

资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗  < 1000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。

注意：
main函数需要返回0;
只使用ANSI C/ANSI C++ 标准;
不要调用依赖于编译环境或操作系统的特殊函数。
所有依赖的函数必须明确地在源文件中 #include <xxx>
不能通过工程设置而省略常用头文件。

提交程序时，注意选择所期望的语言类型和编译器类型。
*/

#include <bits/stdc++.h>

using namespace std;

const long long MOD = 1000000009;

const int maxN = 100005;

int n, k;

vector<long long> pos, neg;//保存正数和负数的列表

long long ans;

/**
 * 将数组a中[start,end]区间内的数连乘起来
 * @param a
 * @param start
 * @param end
 * @param flag
 * @return
 */
long long mul(vector<long long> a, int start, int end) {
    long long ans = 1;

for (int i = start; i <= end; ++i) {
        ans = ans * a[i] % MOD;
    }
    return ans;
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        long long x;
        cin >> x;
        if (x > 0)pos.push_back(x);
        if (x < 0)neg.push_back(x);//只处理正数和负数，0不处理
    }
    sort(pos.begin(), pos.end());
    sort(neg.begin(), neg.end());
/*===========下面开始分类讨论=========*/
    unsigned long sizeSum = pos.size() + neg.size();
//    1.正数和负数的个数不足k，必然有0的存在
    if (sizeSum < k) {
        ans = 0;
    }
//    2.正数和负数的个数恰好为k
    else if (sizeSum == k) {
//      2.1 k与n相等，必须选这k个数，没有0
        if (k == n) {
            ans = mul(pos, 0, pos.size() - 1) * mul(neg, 0, neg.size() - 1) % MOD;
        }
//      2.2 k<n，有0的存在
        else {
//          2.2.1 可得正数解当且仅当:正数全部选中，负数全部选中且为偶数个
            if (neg.size() % 2 == 0) {
                ans = mul(pos, 0, pos.size() - 1) * mul(neg, 0, neg.size() - 1) % MOD;
            } else {
//          2.2.2 负数是奇数个，全部选中结果为负数，不全部选中可得0，结果就是0
                ans = 0;
            }
        }
    } else {
//    3.正数和负数的个数大于k，情况比较复杂
//    sum>k
//      3.1 没有正数,负数和0中选k个
        if (pos.size() == 0) {
            if (k % 2 == 0) {//k是偶数
                ans = mul(neg, 0, k - 1);//正向选k个
            } else {
                if (sizeSum < n)//有0
                    ans = 0;
                else//没有0，必须从所有负数中选奇数个数=》连乘绝对值小的
                    ans = mul(neg, neg.size() - k, neg.size() - 1);//逆向选k个
            }
//      3.2 没有负数
        } else if (neg.size() == 0) {
            ans = mul(pos, pos.size() - k, pos.size() - 1);//逆向选k个
//      3.3 有正数也有负数
        } else {
            int posStart;
            int negEnd;
            if (k >= pos.size()) {//正数不足k个
                //          假定正数全部选中，剩余偶数个负数，等会再来挪动标尺
                if ((k - pos.size()) % 2 == 0) {
                    negEnd = k - pos.size() - 1;//负数选择的截止下标
                    posStart = 0;//正数选择的起始下标
                } else {
                    //          剩余个数是奇数，正数先少选一个
                    posStart = 1;//正数选择的起始下标
                    negEnd = k - pos.size();//负数选择的截止下标
                }
            } else {//正数多余k个，假定从正数中先选最大的k个
//                if(k%2==0){ //k是偶数
                negEnd = -1;
                posStart = pos.size() - k;
//                }else{//k是奇数，先少选一个
//                    negEnd=-1;
//                    posStart = pos.size()-1-k;
//                }
            }
//          双标尺移动
            while (negEnd + 2 < neg.size() && posStart + 2 < pos.size() &&
                   neg[negEnd + 1] * neg[negEnd + 2] > pos[posStart] * pos[posStart + 1]) {
                negEnd += 2;
                posStart += 2;
            }
            ans = mul(neg, 0, negEnd) * mul(pos, posStart, pos.size() - 1) % MOD;
        }
    }

cout << ans << endl;

return 0;
}
```

0.0分

3 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

凡森Zfans

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

母牛的故事（C语言代码）

Hello, world! （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

蓝桥杯2018年第九届真题-乘积最大-题解（C++代码）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

不会做的

Wu-求圆的面积（C++代码）

WU-小九九（C++代码）

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

1908题解

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

1048题解（读入回车问题）

单词个数统计（C语言代码）

凡森Zfans

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

母牛的故事 （C语言代码）

Hello, world! （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

蓝桥杯2018年第九届真题-乘积最大-题解（C++代码）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

不会做的

Wu-求圆的面积 （C++代码）

WU-小九九 （C++代码）

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

1908题解

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

1048题解（读入回车问题）

单词个数统计 （C语言代码）

母牛的故事（C语言代码）

　　评论区

Wu-求圆的面积（C++代码）

WU-小九九（C++代码）

单词个数统计（C语言代码）