2608 問題 E: 藍橋杯2021年第十二屆省賽真題-分果果
時間限制: 1s
內存限制: 128MB 提交: 359 解決: 47
題目描述
小藍要在自己的生日宴會上將 n 包糖果分給 m 個小朋友。每包糖果都要分出去，每個小朋友至少要分一包，也可以分多包。
小藍已經提前將糖果準備好了，為了在宴會當天能把糖果分得更平均一些，小藍要先計算好分配方案。
小藍將糖果從 1 到 n 編號，第 i 包糖果重 wi。小朋友從 1 到 m 編號。每個小朋友只能分到編號連續(xù)的糖果。小藍想了很久沒想出合適的分配方案使得每個小朋友分到的糖果差不多重。因此需要你幫他一起想辦法。為了更好的分配糖果，他可以再買一些糖果，讓某一些編號的糖果有兩份。當某個編號的糖果有兩份時，一個小朋友最多只能分其中的一份。請找一個方案，使得小朋友分到的糖果的最大重量和最小重量的差最小，請輸出這個差。
例如，小藍現在有 5 包糖果，重量分別為 6, 1, 2, 7, 9，如果小藍要分給兩個小朋友，則他可以將所有糖果再買一份，兩個小朋友都分到 1 至 5 包糖果，重量都是 25，差為 0。
再如，小藍現在有 5 包糖果，重量分別為 6, 1, 2, 7, 9，如果小藍要分給三個小朋友，則他可以將第 3 包糖果再買一份，第一個小朋友分 1 至 3 包，第二個小朋友分 3 至 4 包，第三個小朋友分第 5 包，每個小朋友分到的重量都是 9，差為 0。
再如，小藍現在有 5 包糖果，重量分別為 6, 1, 2, 7, 9，如果小藍要分給四個小朋友，則他可以將第 3 包和第 5 包糖果再買一份，仍然可以每個小朋友分到的重量都是 9，差為 0。
再如，小藍現在有 5 包糖果，重量分別為 6, 1, 2, 7, 9，如果小藍要分給五個小朋友，則他可以將第 4 包和第 5 包糖果再買一份，第一個小朋友分第 1 至 2 包重量為 7，第二個小朋友分第 3 至 4 包重量為 9，第三個小朋友分第 4 包重量為 7，第四個和第五個小朋友都分第 5 包重量為 9。差為 2。
輸入
輸入第一行包含兩個整數 n 和 m，分別表示糖果包數和小朋友數量。
第二行包含 n 個整數 w1, w2, · · · , wn，表示每包糖果的重量。
輸出
輸出一個整數，表示在最優(yōu)情況下小朋友分到的糖果的最大重量和最小重
量的差。
提示
【評測用例規(guī)模與約定】
對于 30% 的評測用例，1 ≤ n ≤ 10，1 ≤ m ≤ 10，1 ≤ wi ≤ 10；
對于 60% 的評測用例，1 ≤ n ≤ 30，1 ≤ m ≤ 20，1 ≤ wi ≤ 30；
對于所有評測用例，1 ≤ n ≤ 100，1 ≤ m ≤ 50，1 ≤ wi ≤ 100。在評測數據中，wi 隨機生成，在某個區(qū)間均勻分布。