算法提高最大乘积

2019-11-10 19:41:06

字体：大中小

来源：转载

供稿：网友

算法提高最大乘积时间限制：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;}

上一篇：Spring4.3.x 浅析xml配置的解析过程（1）——使用XmlBeanDefinitionReader解析xml配置

下一篇：I帧 B帧 p帧 IDR帧的区别