11079 可以移动的石子合并（优先做）

时间限制:1000MS 代码长度限制:10KB
提交次数:25 通过次数:9

题型: 编程题 语言: G++;GCC;VC;JAVA

Description

有n堆石子形成一行(a1,a2,…,an，ai为第i堆石子个数)，现要将石子合并成一堆，规定每次可
选择至少2堆最多k堆移出然后合并，每次合并的分值为新堆的石子数。

若干次合并后，石子最后肯定被合并为一堆，得分为每次合并的分值之和。

现在求解将这n堆石子合并成一堆的最低得分和最高得分。

输入格式

两行。第一行n和k。
第二行a1 a2 … an，每个ai(1<=i<=n)表示第i堆石子的个数，n<=200，2<=k<=n。

输出格式

仅一行，为石子合并的最低得分和最高得分，中间空格相连。

输入样例

7 3
45 13 12 16 9 5 22

输出样例

199 593

解题思路

贪心算法

求最大

保证每次选两堆最多的，合并直至只剩一堆为止，能获得最大得分；

求最小

1. 保证每次选k堆最少的，合并直至只剩一堆为止，能获得最小得分。
2. 在合并之前，若 n%(k-1)!=1，说明合并到最后一轮时，剩下不是k堆（而是比k堆少），这样算的并不是最小得分，而必须在合并之前添加若干个为0的虚拟堆，目的为凑成的堆数保证每次都能有k堆合并（包括最后一次）最后合并为1堆。

算法思路

求最大

1. 将数组进行升序排序。
2. 循环遍历，从数组尾部往前不断累加即可（因为每次只合并2堆最大的）。

求最小

1. 按题意要求补0到数组长度满足能整除 k 后，对数组进行降序排序。
2. 从后往前合并，外层 i 循环控制累加到哪里，内层 j 目的为一次累加 k 个石堆，所以通过 b[i - k + 1] += b[i - j] 控制即可，即如果数组为 a = [8, 6, 5, 4, 3, 2, 1, 0, 0]，一次累加3个的话，那就 1 + 0 + 0 = 1 后，索引往前移动3位，继续重复运算，直到加到数组首位。
3. 每次进行完 k 次合并后，都进行得分的累加，同时要对数组重新进行降序排序！因为合并完后可能数字变大不满足原来的降序了。

更多注释可查看下方的完整代码中，有助于理解。

代码如下

#include 
#include /*
7 3
45 13 12 16 9 5 22
*/using namespace std;int a[201]; // 用于求最大得分的数据
int b[201]; // 用于求最小得分的数据
int n, k;
int minNum = 0, maxNum = 0;bool cmp2(int lhs,int rhs)//降序
{return lhs > rhs;
}void Max() {int i;for (i = n - 1; i > 0; i--){a[i - 1] += a[i];maxNum += a[i - 1];}
}void Min() {// 每次合并 k 堆，最后不能刚好合并完时，就得添加到最后一次刚好合并完，即如果差1堆，就得补1个0int i, j;for (i = n - 1; i > 0; i = i - k + 1){// 每次合并 k 堆，然后将合并后的得分记上for(j = 0; j < k - 1; j++) {b[i - k + 1] += b[i - j];}minNum += b[i - k + 1];sort(b, b + i - k + 2, cmp2); // 每次加完后都要重新排序，注意已加过的那些石堆就不用排序了，截止位置为 i - k + 1 的位置再加上一个1，因为是尾部开区间}
}int main()
{int i;cin >> n >> k;for(i = 0; i < n; i++) {cin >> a[i];b[i] = a[i];}sort(a, a + n); // 升序排序Max();while ((n % (k - 1)) != 1) {b[n] = 0;n++;}sort(b, b + n, cmp2);Min();cout << minNum << " " << maxNum << endl;return 0;
}