首页 > 试题广场 >

小美的游戏

[编程题]小美的游戏
  • 热度指数:1336 时间限制: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 次操作之后,最后数组中的元素的总和尽可能大。

输入描述:
一行两个整数 n, k,表示数组的长度和操作的次数。
一行 n 个整数 a_1, a_2, \cdots, a_n,表示数组的元素。
1 \leq k < n \leq 10^5
1 \leq a_i \leq 10^5


输出描述:
输出一个整数,表示最后数组中的元素的总和的最大值,由于答案可能很大,你只需要输出答案对 10^9 + 7 取模的结果。
示例1

输入

5 2
1 2 3 4 5

输出

65

说明

第一次操作后,数组变为 [1, 2, 12, 1, 5]
第二次操作,数组变为 [1, 2, 60, 1, 1]
n, k = map(int , input().split())
a = list(map(int , input().split()))
a.sort(reverse=True)
res = 1
for i in range(k+1):
    res *= a[i]
res += k
res += sum(a[k+1:])
print(res % 1000000007)
发表于 2023-09-12 23:44:50 回复(0)
#include <stdio.h>
#include <stdlib.h>
intcmfun(constvoid*p,constvoid*q){
       return*(long*)p-*(long*)q;
}
intmain() {
    longn,k;
    longa[1000000],sum=0,x,y;
    scanf("%ld%ld",&n,&k);
    for(inti=0;i<n;i++){
        scanf("%ld",&a[i]);
    }
    qsort(a, n, sizeof(long), cmfun);
    for(intj=n-k-1;j<n-1;j++){
        x=1;
        y=a[j]*a[j+1]%(long)(1e9+7);
        a[j]=x;
        a[j+1]=y;
    }
    for(inti=0;i<n;i++){
        sum+=a[i];
    }
    printf("%ld",sum%(long)(1e9+7));
 
}
发表于 2023-09-02 10:33:31 回复(0)
import java.util.Scanner;
import java.util.Arrays;
import java.math.BigInteger;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();
        int k = in.nextInt();
        int[] a = new int[n];

        for(int i = 0; i < n; i++){
            a[i] = in.nextInt();
        }

        Arrays.sort(a);

        // 从后向前遍历
        BigInteger boss = new BigInteger(String.valueOf(a[n - 1]));
        for(int i = n - 2; i > -1 && k > 0; i--){
            BigInteger employee = new BigInteger(String.valueOf(a[i]));
            boss = boss.multiply(employee);
            a[i] = 1;
            k--;
        }

        for(int i = 0; i < n - 1; i++){
            BigInteger employee = new BigInteger(String.valueOf(a[i]));
            boss = boss.add(employee);
        }

        boss = boss.mod(new BigInteger(String.valueOf("1000000007")));

        System.out.println(boss);

    }
}

发表于 2025-03-08 20:45:39 回复(0)
import java.util.*;
import java.io.*;
import java.math.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    private static int mod = 1000000007;
    private static class MaxComparator implements Comparator<BigDecimal>{
        public int compare(BigDecimal o1, BigDecimal o2){
            return o2.compareTo(o1);
        }
    }
     public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] str = bf.readLine().split(" ");
        int n = Integer.parseInt(str[0]);
        int k = Integer.parseInt(str[1]);
        PriorityQueue<BigDecimal> queue = new PriorityQueue<>(new MaxComparator());
        str = bf.readLine().split(" ");
        for(int i=0;i<n;i++){
            queue.offer(new BigDecimal(Long.parseLong(str[i])));
        }

        for(int i=0;i<k;i++){
            BigDecimal first = queue.poll();
            BigDecimal second = queue.poll();
            //System.out.println("first="+first+",second="+second);
            BigDecimal mul = first.multiply(second);
            queue.offer(mul);
            queue.offer(new BigDecimal(1));
        }

        BigDecimal res = new BigDecimal(0);
        while(!queue.isEmpty()){
            BigDecimal curr = queue.poll();
            res = res.add(curr);
        }
        
        System.out.println(res.divideAndRemainder(new BigDecimal(mod))[1]);





    }
}

发表于 2024-09-08 14:49:04 回复(0)
dalao们,我卡24了,为啥哇QAQ
#include <iostream>
#include <queue>
#include <climits>
using namespace std;

const long long MOD = 1e9+7;

int main() {
    int n,k;
    cin>>n>>k;
    long long x;
    priority_queue<long long> q;
    for(int i=0;i<n;i++){
        cin>>x;
        q.push(x);
    }
    while(k--){
        long long a1=q.top();
        q.pop();
        long long a2=q.top();
         q.pop();
        long long tmp=(a1*a2)%MOD;
        q.push(tmp);
        q.push(1);
        
    }
    //cout<<q.size()<<endl;
    long long sum=0;
    while(!q.empty()){
        long long now=q.top();
        q.pop();
        sum=(sum+now)%MOD;
    }
    printf("%lld\n",sum);
}
// 64 位输出请用 printf(\"%lld\")


发表于 2024-08-31 11:35:13 回复(0)
#include <bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef long long ll;
const long long mod=1e9+7;
int n,k;
long long a[100005];
void solve()
{
    cin>>n>>k;
    priority_queue<long long>q;
    long long mx=-1;
    int id=-1;
    long long sum=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(mx==-1)
        {
            mx=a[i];id=i;
        }
        else if(mx<a[i])
        {
            q.push(mx),sum+=mx;    
            mx=a[i];id=i;
        }else q.push(a[i]),sum+=a[i];
    }
    //cout<<q.size()<<" "<<sum<<" "<<mx<<" "<<id<<"\n";
    while(k--&&!q.empty())
    {
        int now=q.top();q.pop();
        sum-=now-1;
        //cout<<now<<" "<<a[id]<<" "<<sum<<"\n";
        a[id]=1ll*a[id]*now%mod;
    }
    cout<<(a[id]+sum)%mod;
}
int main()
{
    IO;
    solve();
    return 0;
}
发表于 2023-10-16 17:05:41 回复(0)

发表于 2023-09-07 18:44:09 回复(0)
Java版本
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {

        long mod = 1000000007;

        Scanner in = new Scanner(System.in);

        int len = in.nextInt();
        int max_op = in.nextInt();
        long res = 0L;
        long sum = 0L;
        long[] a = new long[len];

        for(int i=0;i<len;i++){
            a[i] = in.nextInt();
        }

        Arrays.sort(a);
        int idx = len-1;

        for(int j=1;j<=max_op;j++){

            if(a.length>=2){
                long mul = (a[idx] * a[idx-1])%mod;
               
                a[idx-1] = mul;
                a[idx] = 1;
                idx = idx - 1;
                   
            }else{
                res = Math.max(res, a[0]);
                break;
            }
        }
        for(int j=0;j<len;j++){
            sum = sum + a[j];
        }
       
        res = Math.max(res,sum%mod);
        System.out.print(res);
    }
}

发表于 2023-09-06 15:09:13 回复(0)
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)