技术教程 编程教程 问题 1936: [蓝桥杯][算法提高VIP]最大乘积 正文

问题 1936: [蓝桥杯][算法提高VIP]最大乘积

2023-05-20,,

问题 1936: [蓝桥杯][算法提高VIP]最大乘积

时间限制: 1Sec 内存限制: 128MB 提交: 77 解决: 16

题目描述

对于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 <cstdio>

 #include <algorithm>

 #include <cstdlib>

 #include <cstring>

 #include <string>

 #include <deque>

 #include <vector>

 #include <set>

 using namespace std;

 #define ll long long

 const int N= 5e3+;

 #define P pair<int,int>

 ll n,k,a[N];

 int t;

 int main()

 {

 scanf("%d",&t);

 while(t--)

 {

 scanf("%lld%lld",&n,&k);

 for(ll i=;i<n;i++) scanf("%lld",&a[i]);

 sort(a,a+n);

 ll ans=;

 ll i,j;

 for(i=n-,j=;k>;){

 if(k>=){

 ll ans1 = a[i]*a[i-];

 ll ans2 = a[j]*a[j+];

 if(ans1>=ans2){

 ans*=a[i];

 k--;

 i--;

 }

 else{

 ans*=ans2;

 j+=;

 k-=;

 }

 }

 else{

 ans*=a[i];

 k--;

 }

 }

 printf("%lld\n",ans);

 }

 return ;

 }

问题 1936: [蓝桥杯][算法提高VIP]最大乘积的相关教程结束。

《问题 1936: [蓝桥杯][算法提高VIP]最大乘积.doc》

下载本文的Word格式文档，以方便收藏与打印。

Copyright 2023. 昆居客 - IT编程,互联网信息技术文档大全!