题解 | 数组重乘法贪心解法

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int t = Integer.parseInt(st.nextToken());
        while (t-- > 0) {
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            st = new StringTokenizer(br.readLine());
            int[] nums = new int[n];
            for (int i = 0; i < n; i++) {
                nums[i] = Integer.parseInt(st.nextToken());
            }
            Arrays.sort(nums);
            long sum = 0;
            int l = n - 2;
            int r = n - 1;
            sum += (long) nums[l] * nums[r];
            for (int i = n - 3; i >= 0; i--) {
                if (nums[r] >= nums[l]) {
                    sum += (long) nums[r] * nums[i];
                    r = i;
                } else {
                    sum += (long) nums[l] * nums[i];
                    l = i;
                }
            }
            System.out.println(sum);
        }
    }
}

例子：[1, 2, 3, 4, 5, 6]

排序后通过数学规律可看出，中间必定是最大和次大的相乘，第三大的都是要乘以当前左右最大的值才是最优解，后面都是沿用此思路来维持最优情况。理解后用l和r来记录左右情况，sum来累乘即可。总结来说：把最大的两个放中间，然后依次把剩下的数放在当前较大端点的旁边