AcWing 1239. 乘积最大
原题链接
中等
作者:
sy123
,
2021-01-21 21:25:16
,
所有人可见
,
阅读 331
#include<bits/stdc++.h>
#define mod 1000000009
using namespace std;
const int N=100010;
typedef long long LL;
int a[N];
int n,k;
int main(){
cin>>n>>k;
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
sort(a,a+n);
LL res=1;
if(n==k){ //全部选
for(int i=0;i<n;i++){
res=(res*a[i])%mod;
}
cout<<res%mod;
return 0;
}
//数组里面都是负数
if(a[n-1]<0){ //分奇数偶数-8 -3 -2||-4 -3 -2 -1
if(k%2==1){
for(int i=n-1;i>=n-k;i--){//奇数的话相乘肯定为负数,那么从后往前绝对值比较小
res=(res*a[i])%mod;
}
}
else{
for(int i=0;i<k;i++){
res=(res*a[i])%mod;
}
}
cout<<res<<endl;
return 0;
}
//数组里面有正数
int l=0,r=n-1;
if(k%2==1){//k是奇数
res=a[r--];//取一个数k为偶数
k--;//注意减掉
}
while(k){
LL x=(LL)a[l]*a[l+1],y=(LL)a[r]*a[r-1];//因为x,y可能爆int
if(x>y){
res=x%mod*res%mod;
l+=2;
}
else{
res=y%mod*res%mod;
r-=2;
}
k-=2;
}
cout<<res<<endl;
return 0;
}