首页 > 试题广场 >

小美的游戏

[编程题]小美的游戏

热度指数：1345 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小美有一个长度为 $n$ 的数组，她最多可以进行 $k$ 次操作，每次操作如下：
1. 选择两个整数 $i, j(1 \leq i < j \leq n)$
2. 选择两个整数 $x, y$ ，使得 $x \times y = a_i \times a_j$
3. 将 $a_i$ 替换为 $x$ ，将 $a_j$ 替换为 $y$

她希望最多进行 $k$ 次操作之后，最后数组中的元素的总和尽可能大。

输入描述:

一行两个整数 ，表示数组的长度和操作的次数。
一行  个整数 ，表示数组的元素。

输出描述:

输出一个整数，表示最后数组中的元素的总和的最大值，由于答案可能很大，你只需要输出答案对  取模的结果。

示例1

输入

5 2
1 2 3 4 5

输出

说明

第一次操作后，数组变为 [1, 2, 12, 1, 5]
第二次操作，数组变为 [1, 2, 60, 1, 1]

算法知识视频讲解

Python

StanMarsh

n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
i = n-1
MOD = 10**9 + 7
for _ in range(k):
    x = a[i-1]
    y = a[i]
    a[i-1] = (x*y) % MOD
    a[i] = 1
    i -= 1
res = 0
for ai in a:
    res += ai
    res %= MOD
print(res)

发表于 2023-08-29 22:06:46 回复(0)