牛牛与切割机

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        long minSum = Long.MAX_VALUE;
        int i = 0;
        int[] values = new int[n];
        while(i < n) {
            values[i] = in.nextInt();
            i++;
        }

        if(n == 1) {
            System.out.println(values[0]);
            return;
        }

        long sum = Arrays.stream(values).sum();
        long sum1 = 0;
        long sum2 = sum;


        i = 0;
        while(i < n - 1) {
            
            sum1 += values[i];
            
            sum2 -= values[i];

            minSum = Math.min(minSum, sum1 * sum2);

            i++;
        }

        System.out.println(minSum);
        // 注意 hasNext 和 hasNextLine 的区别
        // while (in.hasNextInt()) { // 注意 while 处理多个 case
        //     int a = in.nextInt();
        //     int b = in.nextInt();
        //     System.out.println(a + b);
        // }
    }
}

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

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();
    }
}

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }

        int[] preSum = new int[n + 1];
        preSum[0] = 0;
        for (int i = 1; i < preSum.length; i++) {
            preSum[i] = arr[i - 1] + preSum[i - 1];
        }
        long sum1 = 0, sum2 = 0;
        long sum = Long.MAX_VALUE;
        for (int i = 0; i < n-1; i++) {
            sum1 = preSum[i + 1] - preSum[0];
            sum2 = preSum[n] - preSum[i + 1];
            sum = Math.min(sum, sum1 * sum2);

        }
        System.out.print(sum);
    }
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    cin >> n;
    vector<long long> prefix;
    long long x;
    prefix.push_back(0);
    for(int i=1;i<=n;i++){
        cin>>x;
        prefix.push_back(prefix.back()+x);
    }
    long long min=LLONG_MAX,sum;
    for(int i=1;i<n;i++){
        sum=prefix[i]*(prefix[n]-prefix[i]);
        if(sum<min)
        min=sum;
    }
    cout<<min;
}

def min_cut_cost(sequence):
    n = len(sequence)
    if n < 2:
        return 0  # 序列长度至少为2才能切割
    
    # 计算序列的总 sum
    total_sum = sum(sequence)
    
    # 计算前缀和并寻找最小代价
    prefix_sum = 0
    min_cost = float('inf')
    
    # 尝试所有可能的切割点（从1到n-1）
    for i in range(n - 1):
        prefix_sum += sequence[i]
        suffix_sum = total_sum - prefix_sum
        cost = prefix_sum * suffix_sum
        
        if cost < min_cost:
            min_cost = cost
    
    return min_cost