首页 > 试题广场 >

小美的游戏

[编程题]小美的游戏

热度指数：1386 时间限制：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]

算法知识视频讲解

有担当的猕猴桃在看机会

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)

赤染sama

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 回复(1)

C/C++

牛客648667511号

#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)

等offer的萝卜

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)

1224foxmail

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)

户庭无尘杂_虚室有余闲

#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)

乌拉啦a

发表于 2023-09-07 18:44:09 回复(0)

倾城之雨2077

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)

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)

提交观点

问题信息

来自：2023年美团秋招编程...

难度：

9条回答 57收藏 2181浏览

小美的游戏

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题