题解 | #小美的游戏#

题意

对于每次操作，选择数组中的两项 和 ，可以用这两个数的积 的其他两个因子（这两个因子的积也要等于 ）替换，求 次操作下，能得到的最大数组的和。

思路

根据 贪心 思想，在每次操作中，要使得替换后的和更大，选择两个数的乘积尽可能大，用 和 去替换原来的两个数字。

为什么用这两个数字去替换呢？

下面就来证明：

根据均值不等式 ，当且仅当 时，等号成立。又因为这个函数是对称的，所以最大值的情况在边界取到。证毕。

具体处理时，顺序并不影响最后的结果，所以可以先对数组进行排序，然后再取出后 项求积，最后求与其他元素的和。

import java.io.*;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.*;

import static java.util.Arrays.deepToString;


public class Main {

    static boolean LOCAL = Boolean.parseBoolean(System.getenv("LOCAL"));
    static boolean TO_FILE = Boolean.parseBoolean(System.getenv("LOCAL"));
    static Scanner sc = new Scanner(System.in);
    static void debug(Object... os) {
        System.err.println(deepToString(os));
    }

    public static void main(String[] args) {

        if (LOCAL) {
            try {
                System.setIn(new FileInputStream("./data/in.txt"));
            } catch (Throwable e) {
                LOCAL = false;
            }
        }

        if (TO_FILE) {
            try {
                System.setOut(new PrintStream("./data/output.txt"));
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
        }

        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task solver = new Task();
        solver.solve(in, out);
        out.close();
    }

    static class Task {
        Random random = new Random(751454315315L + System.currentTimeMillis());
        static final int MAXN = (int)1e6 + 10;
        static final long INF = (long)1e18;
        static final double EPS = 1e-7;
        static final double PI = Math.acos(-1.0);
        static final long MOD = (long)1e9 + 7;

        public void solve(InputReader in, PrintWriter out) {
            int t = 1;
//            t = in.nextInt();
            while (t-- > 0) {
                solveSingle(in, out);
            }
        }

        public void solveSingle(InputReader in, PrintWriter out) {
            int n = in.nextInt(), k = in.nextInt();
            int[] a = new int[n];
            
            for (int i = 0; i < n; i++) a[i] = in.nextInt();
            
            Arrays.sort(a);
            
            long res = 0;
            for (int i = 0; i < n - k - 1; i++) {
                res = (res + a[i]) % MOD;
            }
            
            long mul = 1;
            for (int i = n - 1; i >= n - 1 - k; i--) {
                mul = (mul * a[i]) % MOD;
            }
            res = (res + mul) % MOD;
            
            res = (res + k) % MOD;
            
            out.println(res);
        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public float nextFloat() {
            return Float.parseFloat(next());
        }

        public BigDecimal nextBigDecimal() { return new BigDecimal(next()); }

        public String nextLine(){
            while (tokenizer == null || !tokenizer.hasMoreElements()){
                try{
                    tokenizer = new StringTokenizer(reader.readLine());
                }catch (IOException e){
                    e.printStackTrace();
                }
            }
            return tokenizer.nextToken("\n");
        }

    }
}

复杂度分析

• 时间复杂度：，其中 是数组的大小。除了排序之外，其他操作都是 的。
• 空间复杂度：，其中 是数组的大小。