思路：贪心

为了使得总和最大，每次操作一定是让最大值和次大值相乘，然后将得到的结果作为最大值，再进行计算，直到执行$m$次。

实际操作中可以对原数组进行排序，然后按照上述方式模拟即可。

数据范围较大，C++和Java选手需要注意爆int

时间复杂度

$O(nlogn)$

代码

C++

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;
const int M = 1e6 + 5;
ll a[M];
void T() {
    int n, k;
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", a + i);
    }
    sort(a + 1, a + 1 + n);
    ll ans = 1;
    for (int i = n, j = k; i > 0 && j >= 0; --i, --j) {
        ans = ans * a[i] % mod;
    }
    for (int i = 1; i < n - k; ++i) {
        ans = (ans + a[i]) % mod;
    }
    printf("%lld", (ans + k) % mod);
}

int main() {
    T();
    return 0;
}

python代码

n,m = map(int,input().split())
a = list(map(int,input().split()))

res = 1
a.sort()
for i in range(1,m+2):
    res *= a[-i]
    res %= 1e9 + 7

for j in range(n-m-1):
    res += a[j]
    res %= 1e9+7

print(int(res+m))

Java代码

import java.util.Arrays;
import java.util.Scanner;

public class Main {
        public static void main(String[] args) {
                Scanner scanner = new Scanner(System.in);
                int[] b = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
                int n = b[0], k = b[1];
                //n为数组长度，k为操作次数
                long[] a = Arrays.stream(scanner.nextLine().split(" ")).mapToLong(Long::parseLong).toArray();
                long mod = (long) (1e9 + 7);
                Arrays.sort(a);
                int len = a.length;
                int ptr1 = len - 2, ptr2 = len - 1;
                for(int i = 0; i < k && ptr1 >= 0; i++) {
                        long temp =  (a[ptr1] * a[ptr2]) % mod;
                        a[ptr1] = 1;
                        a[ptr2] = temp;
                        ptr1--;
                }
                long result = 0;
                for(int i = 0; i < len; i++) {
                        result = result + a[i];
                }
                System.out.println(result % mod);
        }
}

题目内容

小美被给定一个长度为$n$的数组，她最多可以进行$m$次操作，每次操作如下:

1.选择两个下标 $i,j(1 <i< j< n)$

2.选择两个整数$x,y$ 满足条件：$x*y = a_i*a_j$

3.$a_i:=x$ , $a_j:=y$

他只能操作$m$ 次 ， 目标是使得最后数组中的元素的总和尽可能大

输入描述

一行两个整数$n,m$ , 表示数组长度和操作次数

一行$n$个整数 $a_1,a_2,...,a_n$

$1\leq m<n \leq 1e5$

$1 \leq a_i \leq 1e5$

输出描述

输出一个整数，表示最后数组中元素总和最大值。

由于答案可能很大，输出取模$1e9 + 7$ 意义下的结果

样例

输入

6 2
1 2 3 4 5 6

输出

128