A7945.接水

普及-

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

小码君正在排队接水,他观察到这里有 nn 位同学想要接水,不妨将这些同学编号为 1n1 \sim n,第 ii 位同学要接 wiw_i 的水。这里总共有 mm 个水龙头,每个水龙头每秒钟的供水量相等,均为 11。同学们按照编号从小到大的顺序依次到水龙头前接水,即刚开始的时候编号为 1m1 \sim m 的同学各占一个水龙头。假设同学们是同时打开水龙头接水,当一名同学接完水之后下一位同学跟上(可以认为换人的过程是瞬间完成的)。

现在给出 nn 名同学的接水量,按照上述接水规则,问所有同学都接完水需要多少秒。

输入格式

第一行两个整数 nnmm,用一个空格隔开,分别表示接水人数和龙头个数。

第二行 nn 个整数 w1,w2,,wnw_1,w_2,\ldots,w_n,每两个整数之间用一个空格隔开,wiw_i 表示 ii 号同学的接水量。

输出格式

一个整数,表示接水所需的总时间。

输入输出样例

  • 输入#1

    5 3
    4 4 1 2 1

    输出#1

    4
  • 输入#2

    8 4
    23 71 87 32 70 93 80 76

    输出#2

    163

说明/提示

【输入输出样例 #1 说明】

11 秒,33 人接水。第 11 秒结束时,1,2,31,2,3 号同学每人的已接水量为 1,31,3 号同学接完水,44 号同学接替 33 号同学开始接水。

22 秒,33 人接水。第 22 秒结束时,1,21,2 号同学每人的已接水量为 2,42,4 号同学的已接水量为 11

33 秒,33 人接水。第 33 秒结束时,1,21,2 号同学每人的已接水量为 3,43,4 号同学的已接水量为 2244 号同学接完水,55 号同学接替 44 号同学开始接水。

44 秒,33 人接水。第 44 秒结束时,1,21,2 号同学每人的已接水量为 4,54,5 号同学的已接水量为 111,2,51,2,5 号同学接完水,即所有人完成接水的总接水时间为 44 秒。

【数据范围】

1n1041 \le n \le {10}^41m1001 \le m \le 100mnm \le n

1wi1001 \le w_i \le 100

【普及组算法2】模拟与枚举

0/19
首页