#1869. A排队打水

    ID: 1869 传统题 1000ms 256MiB 上传者:

A排队打水

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

琦琦的学校每到下课,饮水机总是会排满了前来打水学生。 有 n\red{n(}1<=n<=300000\red{1<=n<=300000)}个学生排队打水。第 i\red{i }个学生打水需要 ti\red{t_i(}1<=ti<=1000000\red{1<=t_i<=1000000)}的时间。 每个学生需要等待他前面的所有学生打完水才能开始打水,请你安排一个打水的顺序,使得所有学生的等待时间的总和 T\red{T }最小 。 输出这个等待总时间T\red{T}。 当然,一台饮水机是完全不够的,为此,学校共修了 m\red{m(}1<=m<=300000\red{1<=m<=300000)}台饮水机。

输入格式

第一行,两个整数,分别是 n\red{n,}m\red{m}。 第二行,n\red{n }个整数,第 i\red{i }个整数表示第 i\red{i }个学生的打水时间 ti\red{t_i}

输出格式

共一行,第一行,一个整数 最小的等待总时间 T\red{T}

样例

输入样例

4 1
4 3 2 1

输出样例

10

花都信息班测试

未参加
状态
已结束
规则
IOI
题目
6
开始于
2023-1-14 18:00
结束于
2023-1-14 21:00
持续时间
3 小时
主持人
参赛人数
6