牛牛与切割机

[题目链接](https://www.nowcoder.com/practice/cda06078a54142d29da7adc3b9ad5880)

思路

有一个序列 $a_1, a_2, \ldots, a_n$ ，将其切割一刀，分成两个非空的连续子序列 $a_1, \ldots, a_k$ 和 $a_{k+1}, \ldots, a_n$ （ $1 \le k < n$ ），切割代价为两部分元素和的乘积。求最小切割代价。

前缀和枚举

设总和为 $S = \sum_{i=1}^{n} a_i$ ，前缀和为 $P_k = \sum_{i=1}^{k} a_i$ 。在位置 $k$ 处切割的代价为：

$ $\text{cost}(k) = P_k \times (S - P_k)$ $

只需遍历所有合法切割点 $k = 1, 2, \ldots, n-1$ ，维护前缀和并计算代价，取最小值即可。

样例演示

输入 $[1, 2, 3, 4, 5]$ ，总和 $S = 15$ ：

切割位置 $k$	左部分和 $P_k$	右部分和 $S - P_k$	代价
1	1	14	14
2	3	12	36
3	6	9	54
4	10	5	50

最小代价为 $14$ 。

复杂度分析

时间复杂度： $O(n)$ ，遍历一次数组计算前缀和并求最小值。
空间复杂度： $O(n)$ ，存储输入数组（也可优化到 $O(1)$ ，边读边算）。

代码

C++
Java

#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<long long> a(n);
    long long total = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        total += a[i];
    }
    long long ans = LLONG_MAX;
    long long prefix = 0;
    for (int i = 0; i < n - 1; i++) {
        prefix += a[i];
        long long cost = prefix * (total - prefix);
        if (cost < ans) ans = cost;
    }
    cout << ans << endl;
    return 0;
}

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] a = new long[n];
        long total = 0;
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextLong();
            total += a[i];
        }
        long ans = Long.MAX_VALUE;
        long prefix = 0;
        for (int i = 0; i < n - 1; i++) {
            prefix += a[i];
            long cost = prefix * (total - prefix);
            if (cost < ans) ans = cost;
        }
        System.out.println(ans);
    }
}