牛牛与切割机

思路

题目在说什么？给一个长度为 的序列，在某个位置切一刀，把序列分成左右两个非空连续段，切割代价定义为左段元素和乘以右段元素和，求最小代价。

设总和为 ，在位置 切割后左段和为 ，右段和为 ，代价为 。

枚举所有 个切割位置，用前缀和维护 ，对每个位置计算 取最小值即可。

从数学角度看， 是一个开口向下的抛物线，在 时取最大值。所以最小值出现在 离 最远的地方，也就是切割尽量靠近两端。但由于序列元素可能有各种取值，直接枚举所有位置更稳妥。

代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    scanf("%d",&n);
    vector<long long> a(n);
    long long total = 0;
    for(int i=0;i<n;i++){
        scanf("%lld",&a[i]);
        total += a[i];
    }
    long long left = 0;
    long long ans = LLONG_MAX;
    for(int i=0;i<n-1;i++){
        left += a[i];
        long long right = total - left;
        ans = min(ans, left * right);
    }
    printf("%lld\n", ans);
    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 left = 0;
        long ans = Long.MAX_VALUE;
        for (int i = 0; i < n - 1; i++) {
            left += a[i];
            long right = total - left;
            ans = Math.min(ans, left * right);
        }
        System.out.println(ans);
    }
}

import sys
input = sys.stdin.readline

def main():
    n = int(input())
    a = list(map(int, input().split()))
    total = sum(a)
    left = 0
    ans = float('inf')
    for i in range(n - 1):
        left += a[i]
        right = total - left
        ans = min(ans, left * right)
    print(ans)

main()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
    const n = parseInt(lines[0]);
    const a = lines[1].split(' ').map(Number);
    let total = 0;
    for (let i = 0; i < n; i++) total += a[i];
    let left = 0;
    let ans = Infinity;
    for (let i = 0; i < n - 1; i++) {
        left += a[i];
        const right = total - left;
        ans = Math.min(ans, left * right);
    }
    console.log(ans);
});

复杂度分析

  • 时间复杂度：，一次遍历计算总和，一次遍历枚举切割位置
  • 空间复杂度：，存储输入数组（可优化到 ，边读边处理）

总结

经典前缀和应用题。核心观察是切割代价 只依赖于左段和，而左段和可以通过逐步累加得到。枚举所有 个切割位置取最小值，整体 即可解决。