8、乘积最大

题目 乘积最大

思路分析

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=1e5+10,mod=1e9+9;

deque<int> a;

int n,k;

int main()

{

	cin>>n>>k;

	for(int i=0;i<n;i++){

		int x;cin>>x;

		a.push_back(x);

	}

	sort(a.begin(),a.end());

	LL sum=1;

	int flag=1;

	if(k&1){//奇数 先拿一个最大的出来

		int v=a.back();

		a.pop_back();

		k--;

		sum=sum*v%mod;

		if(sum<0){//如果最大的也是负数 则最后的结果一定为负

			flag=-1;

		}

	}

//	for(auto t:a)cout<<t<<" ";

	//现在全变成了偶数的情况 直接两头取 看哪对乘积大选哪对 类似于归并

	int T=k/2;

	while(T--){

		int num=a.size()-1;

		LL sum_left=a[0]*a[1]%mod;

		LL sum_right=a[num]*a[num-1]%mod;

		if(sum_left>sum_right){

			sum=sum*sum_left%mod;

			a.pop_front();a.pop_front();

		}

		else{

			sum=sum*sum_right%mod;

			a.pop_back();a.pop_back();

		}

	}

	cout<<flag*sum%mod;

	return 0;

}

负数问题和溢出问题没有考虑细致 导致只过三个数据

写完大概逻辑后得多检查 不能得过且过

代码实现

 #include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=1e5+10,mod=1e9+9;

deque<int> a;

int n,k;

int main()

{

	cin>>n>>k;

	for(int i=0;i<n;i++){

		int x;cin>>x;

		a.push_back(x);

	}

	sort(a.begin(),a.end());

	LL sum=1;

	int flag=1;

	if(k&1){

		int v=a.back();

		a.pop_back();

		k--;

		sum=sum*v%mod;

		if(sum<0){

			flag=-1;

		}

	}

	int T=k/2;

	while(T--){

		int num=a.size()-1;

		LL sum_left=(LL)a[0]*a[1];

		LL sum_right=(LL)a[num]*a[num-1];//这里取模可能会影响大小 注意什么时候取模什么时候不取 别乱加 想清楚

		if(flag*sum_left>flag*sum_right){ //负数要在这里处理 他会影响两边的大小

			sum=sum_left%mod*sum%mod; //乘前乘后都得取模

			a.pop_front();a.pop_front();

		}

		else{

			sum=sum_right%mod*sum%mod;//前后都得取

			a.pop_back();a.pop_back();

		}

	}

	cout<<sum;

	return 0;

}

同类题型

视频讲解

⬅️ 6、日志统计 🏠 00-刷题理模型 ➡️ 第九届 c++ B组 省赛