ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs ContestProblemSetList
Login Register

问题 B: 班级作业本

内存限制：256 MB 时间限制：2 S
题面：传统 评测方式：文本比较 上传者：
提交：44 通过：9
返回比赛提交提交记录

题目描述

  上虞中学初一（3）班的王老师要给班上的同学发批改好的作业本。班上共有 x 名同学，第 i 名同学会在第 ti 分钟走到王老师的讲台前等待领作业本。王老师每次只能同时给一批同学发作业本，发完这批后，需要花 z 分钟整理剩下的作业本（整理期间不能发作业本，整理完后可以立刻开始发下一批）。

所有同学都需要领到作业本，王老师可以任意安排每一批发作业本的开始时间。请问：如何安排才能让所有同学的总等待时间最短？（每位同学的等待时间 = 王老师开始发他那批作业本的时刻 - 他走到讲台前的时刻）

输入格式

第一行包含两个正整数 x,z，以一个空格分开，分别代表班上的同学人数和王老师整理一次作业本需要的时间（分钟）。
第二行包含 x 个非负整数，相邻两数之间以一个空格分隔，第 i 个整数 ti 代表第 i 名同学走到讲台前的时刻。

输出格式

输出一行，一个整数，表示所有同学的总等待时间之和的最小值（单位：分钟）。

输入样例 复制 

5 5  
11 13 1 5 5

输出样例 复制 

4

数据范围与提示

输入样例 1

5 1 

3 4 4 3 5

输出样例 1 

0

样例 1 解释

同学 1 和同学 4 在第 3 分钟走到讲台前，王老师刚好在第 3 分钟开始发第一批，两人等待 0 分钟；发完后花 1 分钟整理，第 4 分钟整理完。
同学 2 和同学 3 在第 4 分钟走到讲台前，王老师立刻开始发第二批，两人等待 0 分钟；整理后第 5 分钟结束。
同学 5 在第 5 分钟走到讲台前，王老师立刻开始发第三批，等待 0 分钟。所有同学都领到作业本，总等待时间为 0。

输入样例 

5 5

11 13 1 5 5

输出样例 2

4

样例 2 解释

王老师这样安排最合理：

  • 同学 3 在第 1 分钟走到讲台前，王老师第 1 分钟开始发第一批，同学 3 等待 0 分钟；发完后整理 5 分钟，第 6 分钟整理完。
  • 同学 4 和同学 5 在第 5 分钟走到讲台前，等王老师整理完，第 6 分钟开始发第二批，两人各等待 1 分钟（6-5=1）；整理后第 11 分钟结束。
  • 同学 1 在第 11 分钟走到讲台前，同学 2 在第 13 分钟走到讲台前，王老师第 13 分钟开始发第三批：同学 1 等待 2 分钟（13-11=2），同学 2 等待 0 分钟。

    总等待时间：0+1+1+2+0=4（这是能达到的最小总等待时间）。



输入：
20 2
85 85 84 96 0 0 85 82 97 83 82 95 85 94 0 0 82 0 83 0
输出
6

数据规模与约定

对于 100% 的数据，x≤500，z≤100，0≤ti≤4×10⁶。 
7128