蓝桥杯最大乘积

48 

 一般人的思路都是想排序后取最大的m个数的乘积，然而应该注意到有时候负数与负数相乘所得的正数更大，因此得改变思维策略。

 如果要取的数m是偶数的话，从小到大排序后，依次从后面和从前面取两个数的乘积进行比较，如果较大两个数的乘积更大，理所当然取这两个数，如果较小的两个数乘积更大，说明这两个数一定是负数，既然相乘后是一个很大的正数，因此可以同时去取这两个数。这样下去直到取满m个数为止。

 如果要取得数是奇数的话，把排序后最大的那个数a[n-1]单独拿出来，如果它是正数的话，对剩下n-1(偶数)个数同样用之前的方法进行取数，取m-1个，再乘以a[n-1]就是最大乘积。如果a[n-1]是负数，则对剩下的n-1(偶数)个数中取出一个绝对值最大的负数，实际上就是构造最小乘积，按照和之前相反的方法去做。

 具体见代码。

#include
#include
using namespace std;
int main()
{
    int t,n,m;
    int a[15];
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(int i=0; i            scanf("%d",&a[i]);
        sort(a,a+n);
        int ans=1,zheng,ni,pos1=0,pos2=n-1;
        if(m%2==0)
        {
            while(m>0)
            {
                zheng=a[pos1]*a[pos1+1];
                ni=a[pos2]*a[pos2-1];
                if(zheng>ni)
                {
                    ans*=zheng;
                    pos1+=2;
                    m-=2;
                }
                else
                {
                    ans*=ni;
                    pos2-=2;
                    m-=2;
                }
            }
        }
        else
        {
            m-=1;
            pos2=n-2;
            if(a[n-1]>0)
            {
                while(m>0)
                {
                    zheng=a[pos1]*a[pos1+1];
                    ni=a[pos2]*a[pos2-1];
                    if(zheng>ni)
                    {
                        ans*=zheng;
                        pos1+=2;
                        m-=2;
                    }
                    else
                    {
                        ans*=ni;
                        pos2-=2;
                        m-=2;
                    }
                }
                ans*=a[n-1];
            }
            else
            {
                while(m>0)
                {
                    zheng=a[pos1]*a[pos1+1];
                    ni=a[pos2]*a[pos2-1];
                    if(zheng                    {
                        ans*=zheng;
                        pos1+=2;
                        m-=2;
                    }
                    else
                    {
                        ans*=ni;
                        pos2-=2;
                        m-=2;
                    }
                }
                ans*=a[n-1];
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}