A22933. 选数
填空题
困难
知识点
题目描述
选数
题目描述
给你两个数 N,K，从 N 个数中选出 K 个使得乘积最大。输出乘积在数学意义上对 109+7 取模的值。
输入格式
第一行：两个整数N,K
第二行：N个整数a1 a2…an
输出格式
一个整数表示答案
输入样例#1
4 2
1 2 -3 -4输出样例#1
12输入样例#2
10 10
1000000000 100000000 10000000 1000000 100000 10000 1000 100 10 1输出样例#2
999983200数据范围
1≤K≤N≤2×105, −109≤ai≤109
参考答案
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int n,k;
long long a[N];
int main()
{
scanf("%d%d",&n,&k);
for (int i = 1; i <= n; i++)
scanf("%lld",&a[i]);
sort(a + 1,a + n + 1);
long long res = 1;
int left = 1,right = n;
int sign = 1;
if (k % 2 == 1)
{
res = a[right];
right--; k--;
if (res < 0) sign = -1;
}
while (k > 0)
{
long long left_product = a[left] * a[left + 1];
long long right_product = a[right] * a[right - 1];
if (left_product * sign > right_product * sign)
{
res = res * (left_product % mod) % mod;
left += 2;
}
else
{
res = res * (right_product % mod) % mod;
right -= 2;
}
k -= 2;
}
res = (res % mod + mod) % mod;
printf("%lld\n",res);
}
上一题
下一题