贪心算法，ac不了，好难受

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

提示

对于 $40%$ 的数据，$1\le K\le N\le 100$。

对于 $60%$ 的数据，$1\le K \le 1000$。

对于 $100%$ 的数据，$1\le K\le N\le 10^5$，$-10^5\le A_i\le 10^5$。

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

洛谷上ac不了，但是测试案例能过，请指出我的错误

Answer 1

#include<iostream>
#include<algorithm>
using namespace std;
 
const int N = 100005;
const int MOD = 1e9+9;
typedef long long ll;
int n,k;
int l,r;
ll a[N];
ll ans=1;
 
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;++i) cin>>a[i];
 
    sort(a+1,a+n+1);
 
    if(n==k)
    {
        for(int i=1;i<=n;++i) ans=(ans*a[i])%MOD;
    }
    else if(k%2==0)
    {
        l=1,r=n;
        for(int i=0;i<k/2;i++)
        {
            if(a[l]*a[l+1]>=a[r]*a[r-1])
            {
                ans=(ans*a[l])%MOD;
                ans=(ans*a[l+1])%MOD;
                l+=2;
            }
            else
            {
                ans=(ans*a[r])%MOD;
                ans=(ans*a[r-1])%MOD;
                r-=2;
            }
        }
    }
    else
    {
        if(a[n]<0)
        {
            for(int i=0;i<k;i++)
            {
                ans=(ans*a[n-i])%MOD;
            }
        }
        else
        {
            ans=a[n];
            l=1,r=n-1;
            for(int i=0;i<k/2;i++)
            {
                if(a[l]*a[l+1]>=a[r]*a[r-1])
                {
                    ans=(ans*a[l])%MOD;
                    ans=(ans*a[l+1])%MOD;
                    l+=2;
                }
                else
                {
                    ans=(ans*a[r])%MOD;
                    ans=(ans*a[r-1])%MOD;
                    r-=2;
                }
            }
        }
    }
 
    cout<<ans<<endl;
 
    return 0;
}