算法提高 最大乘積 時間限制：1.0s 內(nèi)存限制：512.0MB 提交此題 問題描述 對于n個數(shù)，從中取出m個數(shù)，如何取使得這m個數(shù)的乘積最大呢？ 輸入格式 第一行一個數(shù)表示數(shù)據(jù)組數(shù) 每組輸入數(shù)據(jù)共2行： 第1行給出總共的數(shù)字的個數(shù)n和要取的數(shù)的個數(shù)m，1<=n<=m<=15， 第2行依次給出這n個數(shù)，其中每個數(shù)字的范圍滿足:a[i]的絕對值小于等于4。 輸出格式 每組數(shù)據(jù)輸出1行，為最大的乘積。 樣例輸入 1 5 5 1 2 3 4 2 樣例輸出 48
這個做法比較機智= = 負數(shù)一定要選倆 正數(shù)只用選一個
#include <iostream>#include <algorithm>#include<cstdio>#include<cstring>using namespace std;int a[100000];int main(){ int t; cin>>t; while(t--) { int n,m; cin>>n>>m; for(int i=0;i<n;i++) { cin>>a[i]; } sort(a,a+n); int i=0,j=n-1; int s=1; while(m>0) { if(a[i]*a[i+1]>a[j]*a[j-1]&&a[i]<0&&a[i+1]<0)//負數(shù)選倆 { s*=a[i]*a[i+1]; i+=2; m-=2; } else//正數(shù)選一個 { s*=a[j]; j-=1; m-=1; } } cout<<s<<endl; } return 0;}新聞熱點
疑難解答
