题解 | #牛牛与切割机#

题目链接

牛牛与切割机

题目描述

给定一个长度为 $n$ 的序列 $a$ 。将这个序列切割一刀，划分为两个非空的子序列。切割的代价定义为两个子序列元素和的乘积。求最小的切割代价。

解题思路

本题要求找到一个切割点，使得左右两边子序列元素和的乘积最小。

假设我们在第 $i$ 个元素之后进行切割（ $1 \le i < n$ ）。

左边的子序列是 $a_1, a_2, \dots, a_i$ 。
右边的子序列是 $a_{i+1}, a_{i+2}, \dots, a_n$ 。

设左边子序列的和为 $\text{sum}_{left}(i) = \sum_{j=1}^{i} a_j$ 。

设右边子序列的和为 $\text{sum}_{right}(i) = \sum_{j=i+1}^{n} a_j$ 。

那么，在第 $i$ 个元素后切割的代价就是 $\text{cost}(i) = \text{sum}_{left}(i) \cdot \text{sum}_{right}(i)$ 。

我们的目标就是找到一个 $i$ （从 1 到 $n-1$ ），使得 $\text{cost}(i)$ 最小。

一个朴素的想法是，遍历所有可能的切割点 $i$ (from 1 to $n-1$ )：

对于每个 $i$ ，计算左边和 $\text{sum}_{left}(i)$ 。
计算右边和 $\text{sum}_{right}(i)$ 。
计算乘积，并与当前记录的最小代价进行比较。

这样做的时间复杂度是 $O(n^2)$ ，因为每次计算子序列和都需要 $O(n)$ 的时间。

为了优化计算，我们可以使用前缀和。首先，计算整个序列的总和 $\text{total\_sum}$ 。然后，我们再次遍历所有可能的切割点 $i$ ：

在遍历过程中，我们可以维护一个变量 left_sum，表示当前左边子序列的和。
当我们从切割点 $i-1$ 移动到 $i$ 时，left_sum 只需要加上 $a_i$ 即可。
右边子序列的和可以直接通过 right_sum = total_sum - left_sum 得到。
计算代价 left_sum * right_sum，并更新全局的最小代价。

通过这种方式，我们可以在一次遍历中计算出所有切割点的代价，总时间复杂度降为 $O(n)$ 。

算法步骤：

计算整个数组的总和 $\text{total\_sum}$ 。
初始化 min_cost 为一个非常大的数（例如 LLONG_MAX）。
初始化 left_sum 为 0。
遍历数组（从 $i=0$ 到 $n-2$ ，对应切割点在 $a_1$ 到 $a_{n-1}$ 之后）：

a. 更新 left_sum，加上当前元素 $a_i$ 。

b. 计算 right_sum = total_sum - left_sum。

c. 计算当前代价 cost = left_sum * right_sum。

d. 更新 min_cost = min(min_cost, cost)。
输出 min_cost。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <limits>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<long long> a(n);
    long long total_sum = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        total_sum += a[i];
    }

    long long min_cost = numeric_limits<long long>::max();
    long long left_sum = 0;

    // 遍历 n-1 个可能的切割点
    for (int i = 0; i < n - 1; ++i) {
        left_sum += a[i];
        long long right_sum = total_sum - left_sum;
        min_cost = min(min_cost, left_sum * right_sum);
    }

    cout << min_cost << "\n";

    return 0;
}

import java.util.Scanner;
import java.lang.Math;

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 totalSum = 0;

        for (int i = 0; i < n; i++) {
            a[i] = sc.nextLong();
            totalSum += a[i];
        }

        long minCost = Long.MAX_VALUE;
        long leftSum = 0;

        // 遍历 n-1 个可能的切割点
        for (int i = 0; i < n - 1; i++) {
            leftSum += a[i];
            long rightSum = totalSum - leftSum;
            minCost = Math.min(minCost, leftSum * rightSum);
        }

        System.out.println(minCost);
    }
}

import sys

def main():
    n = int(sys.stdin.readline())
    a = list(map(int, sys.stdin.readline().split()))
    
    total_sum = sum(a)
    
    min_cost = float('inf')
    left_sum = 0
    
    # 遍历 n-1 个可能的切割点
    for i in range(n - 1):
        left_sum += a[i]
        right_sum = total_sum - left_sum
        min_cost = min(min_cost, left_sum * right_sum)
        
    print(min_cost)

if __name__ == "__main__":
    main()

算法及复杂度

算法：前缀和思想优化遍历
时间复杂度： $O(n)$ 。需要一次遍历计算总和，再一次遍历寻找最小代价。
空间复杂度： $O(n)$ ，用于存储输入的数组。如果可以边读边计算总和，空间复杂度可以优化到 $O(1)$ （不考虑输入数组本身）。