题目描述
有 n 个学生,第 i 个学生希望在第 ti 天或之前得知课程的成绩。如果在第 ti 天成绩没有公布,他就会等待,每等待一天就会产生 C 不愉快度。请你编写程序,根据输入的 m,计算当成绩在第 1 天到第 m 天公布时,所有学生的不满意度之和分别是多少。
输入
第一行三个正整数 n, m, C (1≤n,m≤20000, 1≤C≤100),分别表示学生的数量是 n,询问的天数是 m,每等待一天就会产生 C 不愉快度。第二行 n 个正整数,表示每个学生希望的公布成绩的时间。
输出
输出一行 m 个空格隔开的整数,第 i 个整数表示当成绩在第 i 天公布时,最小的不愉快度之和。
样例输入
4 4 2
5 1 2 3
样例输出
0 2 6 12
提示
提示:
【伪代码】
将 t 数组从小到大排序
for (int i = 1; i <= n; i++)
计算 t 数组前 i 项的前缀和 s[i]
k = 0
for (int i = 1; i <= m; i++)
{
while (k < n && 第 k + 1 个人需要等待)
k++
输出第 i 天公布成绩时的不愉快度总和
}