2608 問題 E: 藍(lán)橋杯2021年第十二屆省賽真題-分果果
時(shí)間限制: 1s
內(nèi)存限制: 128MB 提交: 359 解決: 47
題目描述
小藍(lán)要在自己的生日宴會(huì)上將 n 包糖果分給 m 個(gè)小朋友。每包糖果都要分出去，每個(gè)小朋友至少要分一包，也可以分多包。 小藍(lán)已經(jīng)提前將糖果準(zhǔn)備好了，為了在宴會(huì)當(dāng)天能把糖果分得更平均一些，小藍(lán)要先計(jì)算好分配方案。 小藍(lán)將糖果從 1 到 n 編號，第 i 包糖果重 wi。小朋友從 1 到 m 編號。每個(gè)小朋友只能分到編號連續(xù)的糖果。小藍(lán)想了很久沒想出合適的分配方案使得每個(gè)小朋友分到的糖果差不多重。因此需要你幫他一起想辦法。為了更好的分配糖果，他可以再買一些糖果，讓某一些編號的糖果有兩份。當(dāng)某個(gè)編號的糖果有兩份時(shí)，一個(gè)小朋友最多只能分其中的一份。請找一個(gè)方案，使得小朋友分到的糖果的最大重量和最小重量的差最小，請輸出這個(gè)差。 例如，小藍(lán)現(xiàn)在有 5 包糖果，重量分別為 6, 1, 2, 7, 9，如果小藍(lán)要分給兩個(gè)小朋友，則他可以將所有糖果再買一份，兩個(gè)小朋友都分到 1 至 5 包糖果，重量都是 25，差為 0。 再如，小藍(lán)現(xiàn)在有 5 包糖果，重量分別為 6, 1, 2, 7, 9，如果小藍(lán)要分給三個(gè)小朋友，則他可以將第 3 包糖果再買一份，第一個(gè)小朋友分 1 至 3 包，第二個(gè)小朋友分 3 至 4 包，第三個(gè)小朋友分第 5 包，每個(gè)小朋友分到的重量都是 9，差為 0。 再如，小藍(lán)現(xiàn)在有 5 包糖果，重量分別為 6, 1, 2, 7, 9，如果小藍(lán)要分給四個(gè)小朋友，則他可以將第 3 包和第 5 包糖果再買一份，仍然可以每個(gè)小朋友分 到的重量都是 9，差為 0。 再如，小藍(lán)現(xiàn)在有 5 包糖果，重量分別為 6, 1, 2, 7, 9，如果小藍(lán)要分給五個(gè)小朋友，則他可以將第 4 包和第 5 包糖果再買一份，第一個(gè)小朋友分第 1 至 2 包重量為 7，第二個(gè)小朋友分第 3 至 4 包重量為 9，第三個(gè)小朋友分第 4 包重量為 7，第四個(gè)和第五個(gè)小朋友都分第 5 包重量為 9。差為 2。
輸入
輸入第一行包含兩個(gè)整數(shù) n 和 m，分別表示糖果包數(shù)和小朋友數(shù)量。 第二行包含 n 個(gè)整數(shù) w1, w2, · · · , wn，表示每包糖果的重量。
輸出
輸出一個(gè)整數(shù)，表示在最優(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。在評測數(shù)據(jù) 中，wi 隨機(jī)生成，在某個(gè)區(qū)間均勻分布。
C
C++
Java
Python
PHP
代碼重置
開啟O2優(yōu)化