题解 | 牛牛与切割机-Java

设做序列和为x，总序列和为常数k，则右序列和为k-x；

即问题可等价为：求y=x(k-x)=-x^2+xk的最小值，抛物线开口向下，则其最小值必在两个端点处取得。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        long[] arr = new long[n];
        long totalSum = 0; // 存储序列总元素和
        
        // 读取序列元素并计算总 sum
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
            totalSum += arr[i];
        }
        
        // 计算两个端点切割的代价
        // 切割点1：左序列仅含第1个元素，右序列含剩余n-1个元素
        long cost1 = arr[0] * (totalSum - arr[0]);
        // 切割点2：左序列含前n-1个元素，右序列仅含最后1个元素
        long cost2 = (totalSum - arr[n - 1]) * arr[n - 1];
        
        // 取两个代价的最小值作为结果
        long minCost = Math.min(cost1, cost2);
        System.out.println(minCost);
        
        in.close(); 
    }
}