算法提高 最大乘積 時間限制：1.0s 內存限制：512.0MB 提交此題 問題描述 對于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>#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)//負數選倆 { s*=a[i]*a[i+1]; i+=2; m-=2; } else//正數選一個 { s*=a[j]; j-=1; m-=1; } } cout<<s<<endl; } return 0;}新聞熱點
疑難解答
