给定 \(N\) 个整数 \(A_1,A_2,…A_N\)。
请你从中选出 \(K\) 个数,使其乘积最大。
请你求出最大的乘积,由于乘积可能超出整型范围,你只需输出乘积除以 \(1000000009\) 的余数。
注意,如果 \(X<0\), 我们定义 \(X\) 除以 \(1000000009\) 的余数是负\((−X)\)除以 \(1000000009\) 的余数,即:\(0−((0−x)%1000000009)\)
第一行包含两个整数 \(N\) 和 \(K\)。
以下 \(N\) 行每行一个整数 \(A_i\)。
输出一个整数,表示答案。
\(1≤K≤N≤10^5,\)
\(−10^5≤Ai≤10^5\)
5 3 -100000 -10000 2 100000 10000
999100009
5 3 -100000 -100000 -2 -100000 -100000
-999999829
模拟
先排序,分情况讨论:
\(k=n\) 时,所有数都选
\(k<n\) 时,
时间复杂度:\(O(nlogn)\)
// Problem: 乘积最大 // Contest: AcWing // URL: https://www.acwing.com/problem/content/description/1241/ // Memory Limit: 64 MB // Time Limit: 1000 ms // // Powered by CP Editor (https://cpeditor.org) // %%%Skyqwq #include <bits/stdc++.h> //#define int long long #define help {cin.tie(NULL); cout.tie(NULL);} #define pb push_back #define fi first #define se second #define mkp make_pair using namespace std; typedef long long LL; typedef pair<int, int> PII; template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; } template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; } template <typename T> void inline read(T &x) { int f = 1; x = 0; char s = getchar(); while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); } while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar(); x *= f; } const int mod=1000000009; int n,k,a[100005]; int main() { cin>>n>>k; for(int i=1;i<=n;i++)cin>>a[i]; sort(a+1,a+1+n); int l=1,r=n,res=1,sign=1; if(k&1) { if(a[r]<0)sign=-1; res=a[r--]; k--; } while(k) { if(1ll*sign*a[l]*a[l+1]>1ll*sign*a[r]*a[r-1]) { res=1ll*res*a[l]%mod*a[l+1]%mod; l+=2; } else { res=1ll*res*a[r]%mod*a[r-1]%mod; r-=2; } k-=2; } cout<<res%mod; return 0; }