蓝桥，贪心算法，测试二过不了

Question

[蓝桥杯 2018 省 B] 乘积最大

题目描述

给定 $N$ 个整数 $A_1, A_2,\cdots, A_N$。请你从中选出 $K$ 个数，使其乘积最大。

请你求出最大的乘积，由于乘积可能超出整型范围，你只需输出乘积除以 $1000000009$（即 $10^9+9$）的余数。

注意，如果 $X<0$， 我们定义 $X$ 除以 $1000000009$ 的余数是 $0-((0-x)\bmod 1000000009)$。

输入格式

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

以下 $N$ 行每行一个整数 $A_i$。

输出格式

一个整数，表示答案。

样例 #1

样例输入 #1

5 3 
-100000   
-10000   
2   
100000  
10000

样例输出 #1

999100009

样例 #2

样例输入 #2

5 3 
-100000   
-100000   
-2   
-100000  
-100000

样例输出 #2

-999999829

```c++

#include <iostream>
#include <algorithm>
using namespace std;
int arr[100001];
int main()
{
    int n,k,s=0;
    long long ans=1;
    cin>>n>>k;
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
    }
    int l=1;
    sort(arr,arr+n);
    if(k%2==1)
    {
        ans=arr[n-1];
        s=1;
        if(ans<0)
        {
            l=-1;
        }
        for(int i=0,j=n-2;i<=j;)
        {
            long long  p=(arr[i]*arr[i+1])%1000000009;
            long long  q=(arr[j]*arr[j-1])%1000000009;
            if(s==k)
            {
                cout<<ans;
                return 0;
            }
            if(p*l>=q*l)
            {
                ans*=p%1000000009;
                i=i+2;
                s=s+2;
            }
            else
            {
                ans*=q%1000000009;
                j=j-2;
                s=s+2;
            }
        }
    }
    else 
    {
        for(int i=0,j=n-1;i<=j;)
        {
            long long  p=arr[i]*arr[i+1]%1000000009;
            long long  q=arr[j]*arr[j-1]%1000000009;
            if(s==k)
            {
                cout<<ans;
                return 0;
            }
            if(p>=q)
            {
                ans*=p%1000000009;
                i=i+2;
                s=s+2;
            }
            else
            {
                ans*=q%1000000009;
                j=j-2;
                s=s+2;
            }
        }
    }
        cout<<ans;
    return 0;
}

不知道哪里出了问题

Answer 1

【相关推荐】

• 帮你找了个相似的问题, 你可以看下: https://ask.csdn.net/questions/246252

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^