首页 > 试题广场 >

牛牛与切割机

[编程题]牛牛与切割机
  • 热度指数:3154 时间限制: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),牛牛切割的代价为两个序列元素和的乘积。牛牛想知道切割代价最小是多少。

输入描述:
第一行输入一个整数 n,表示序列的长度 2 \leq n \leq 10^6
第二行输入 n 个整数 a_1, a_2, \dots, a_n,表示序列的元素 -10^3 \leq a_i \leq 10^3


输出描述:
输出一个整数表示切割代价最小是多少。
示例1

输入

5
1 2 3 4 5

输出

14

说明

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

输入

4
2 1 3 4

输出

16

说明

序列被划分为 2 和 1 3 4。
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void async function () {
    let n,list
    while(line = await readline()){
        if(n){
            list = line.split(' ').map(item=>parseInt(item))
        }else{
            n = parseInt(line)
        }
    }
    let minn = Infinity,right=list.reduce((pre,curr)=>pre+curr,0),left=0
    for(let i=0;i<list.length-1;i++){
        left+=list[i]
        right-=list[i]
        minn = Math.min(minn,left*right)
    }
    console.log(minn)
}()
发表于 2025-12-09 14:41:58 回复(0)