首页 > 试题广场 >

牛牛与切割机

[编程题]牛牛与切割机

热度指数：70 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

有一个序列 $a_1, a_2, ..., a_n$ ，牛牛将对这个序列切割一刀（划分分成两个不相交的非空序列，一个序列为 $a_1, \dots, a_p$ ，另一个序列为 $a_{p+1}, \dots, a_n$ ），牛牛切割的代价为两个序列元素和的乘积。牛牛想知道切割代价最小是多少。

输入描述:

第一行输入一个整数 ，表示序列的长度 。
第二行输入  个整数 ，表示序列的元素 。

输出描述:

输出一个整数表示切割代价最小是多少。

示例1

输入

5
1 2 3 4 5

输出

说明

序列被划分为1 和 2 3 4 5，右边和为 14。

示例2

输入

4
2 1 3 4

输出

说明

序列被划分为 2 和 1 3 4。

算法知识视频讲解

一笑而过2222

#include <iostream> #include <vector> #include <algorithm> int main() { int n; std::cin >> n; std::vector<int> a(n); for (int i = 0; i < n; ++i) { std::cin >> a[i]; } long long total_sum = 0; for (int i = 0; i < n; ++i) { total_sum += a[i]; } long long cost1 = a[0] * (total_sum - a[0]); long long cost2 = (total_sum - a[n-1]) * a[n-1]; long long min_product = std::min(cost1, cost2); std::cout << min_product << std::endl; return 0; }</int></algorithm></vector></iostream>

发表于 2025-06-18 10:50:10 回复(1)

牛客953130736号

从数学上来说，cost(p)=left(p)×(total−left(p))=left(p)⋅(total−left(p)) 也就是cost是一个f(x)=x(total−x)=−x^2+k⋅x的抛物线，中间只有最大值，最小值在两头，因此只需要将最左边的切一刀或者最右边切一刀，然后比较最小值即可。因此这道题没啥意义！

发表于 2025-06-18 09:41:25 回复(0)