问题描述
对于n个数，从中取出m个数，如何取使得这m个数的乘积最大呢？
输入格式
第一行一个数表示数据组数 每组输入数据共2行： 第1行给出总共的数字的个数n和要取的数的个数m，1<=n<=m<=15， 第2行依次给出这n个数，其中每个数字的范围满足:a[i]的绝对值小于等于4。
输出格式
每组数据输出1行，为最大的乘积。
样例输入
1 5 5 1 2 3 4 2
样例输出
48
#include<iostream> #include<algorithm> using namespace std; int n,m; int a[20]; /* 两边的绝对值最大，所以先从两边挑 负数一次得挑两个 乘积相同的时候优先挑负数 */ int main() { int t; cin>>t; while(t--) { cin>>n>>m; for(int i=1;i<=n;++i) cin>>a[i]; sort(a+1,a+1+n); int sum=1; for(int i=n,j=1;i>=j&&m;i--) { int pos=a[i]*a[i-1]; int neg=a[j]*a[j+1]; if(neg>=pos&&m>=2) { sum*=neg; j+=2; m-=2; i++; } else { sum*=a[i]; m--; } } cout<<sum<<endl; } return 0; }