代码编织梦想

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 <iostream>
#include <algorithm>

/*
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个0
    int 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;
}


版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_53893220/article/details/127971336

楼天城楼教主的acm心路历程 ---- 抄自网上_joey丶sunk的博客-爱代码爱编程

其实是转载,,这是楼教主写的(网上发现) 看完好生感动!!好生励志!! 分割线--------------------------------------------------------------------------分割线----------------------------------------------------------

oi、acm大佬楼天城的回忆录_cometoj海上钢琴师的博客-爱代码爱编程

ACRush 楼天城 回忆录 2016年03月17日 19:41:39 Adherer 阅读数:5457 利用假期空闲之时,将这几年GCJ,ACM,TopCoder 参加的一些重要比赛作个 回顾。昨天是GCJ2006 的回

SCAU ACM校队寒训题 DP专题-爱代码爱编程

A - String Partition 动态规划思想:1.外层循环遍历下标,内层循环遍历一遍当前下标前十个数(int大小就是10位)。 2.dp[i]就表示当前下标下的sum最大值,那么内层循环就相当于是“分割”,把i之前的元素切成左右两部分,dp[j-1]部分及j-i部分,后者就是要额外算的,而前面j-1部分因为已经遍历过了所以已经是存好的。

SCAU 算法设计与分析 OJ复习-爱代码爱编程

8594 有重复元素的排列问题(优先做) 时间限制:1000MS 代码长度限制:10KB 提交次数:1610 通过次数:656 题型: 编程题 语言: G++;GCC;VC;JAVA Description 设集合R={r1,r2,…,rn}是要进行排列的n个元素,其中r1,r2,…,rn可能相同。 试着设计一个算法,列出R的所有不同排列。 即,给定

算法分析与设计oj复习题-爱代码爱编程

8594 有重复元素的排列问题(优先做) 时间限制:1000MS 代码长度限制:10KB 提交次数:1610 通过次数:656 题型: 编程题 语言: G++;GCC;VC;JAVA Description 设集合R={r1,r2,…,rn}是要进行排列的n个元素,其中r1,r2,…,rn可能相同。 试着设计一个算法,列出R的所有不同排列。 即,给定n

11079 可以移动的石子合并(优先做)(贪心,非递归)-爱代码爱编程

Description 有n堆石子形成一行(a1,a2,…,an,ai为第i堆石子个数),现要将石子合并成一堆,规定每次可 选择至少2堆最多k堆移出然后合并,每次合并的分值为新堆的石子数。 若干次合并后,石子最后肯定被合并为一堆,得分为每次合并的分值之和。 现在求解将这n堆石子合并成一堆的最低得分和最高得分。 输入格式 两

算法设计与分析 scau11078 不能移动的石子合并(优先做)_smoothzjc的博客-爱代码爱编程

11078 不能移动的石子合并(优先做) 时间限制:1000MS 代码长度限制:10KB 提交次数:0 通过次数:0 题型: 编程题 语言: G++;GCC;VC;JAVA Description 做如下两个模型的

11079 可以移动的石子合并(优先做)_ms_mudrock的博客-爱代码爱编程

11079 可以移动的石子合并(优先做) 时间限制:1000MS  代码长度限制:10KB 提交次数:0 通过次数:0 题型: 编程题   语言: G++;GCC;VC;JAVA Description 有n堆石子形成一行(a1,a2,…,an,ai为第i堆石子个数),现要将石子合并成一堆,规定每次可 选择至少2堆最多k堆移出然后合并,每次合并的分值

一个数组的异或和是指数组中所有的数异或在一起的结果,给定一个数组arr,求最大子数组异或和。_朂後 哋箹萣的博客-爱代码爱编程

问题描述:         一个数组的异或和是指数组中所有的数异或在一起的结果,给定一个数组arr,求最大子数组异或和。 异或运算规则:         异或也叫半加运算,其运算法则相当于不带进位的二进制加法:二进制下用1表示真,0表示假,则异或的运算法则为:0⊕0=0,1⊕0=1,0⊕1=1,1⊕1=0(同为0,异为1),这些法则与加法是相同的

11.20二叉树基础题型_小白孙在路上的博客-爱代码爱编程

一.二叉树的存储 1.存储结构 存储结构:顺序存储或者是类似于链表的链式存储 二叉树的链式存储是通过一个一个的节点引用起来的,常见的表示方式有二叉和三叉表示方式 // 孩子表示法 class Node { int val; // 数据域 Node left; // 左孩子的引用,常常代表左孩子为根的整棵左子树 Node right; /

代码随想录刷题|leetcode 343. 整数拆分 96.不同的二叉搜索树_symdunstaz的博客-爱代码爱编程

目录 343. 整数拆分 思路 整数拆分 96.不同的二叉搜索树 思路 不同的二叉搜索树 343. 整数拆分 题目链接:力扣 思路         动态规划的题目虽然说是要先确定dp数组的含义,再确定递归公式,但是总感觉这两者是相辅相成的,是一起出来的,但是到此,dp数组代表的都是我们要求取

b=a++和b=++a区别及a=++a、a=a++区别_大渔歌_的博客-爱代码爱编程

b=a++是先把a的值赋给b,然后a自加1; b=++a是a先自加1,在把值赋给b b=a++ public static void a(){ int a=1; int b=1; for(int i=0;i<5;i++){ b=a++; } S

(一)逻辑回归及其代价函数 --- 吴恩达深度学习笔记_奕星星奕的博客-爱代码爱编程

逻辑回归 — 适用于二分类问题 使用逻辑回归算法会得到的输出标签y,y在监督问题中全是0或者1,因此这是一种针对二分类问题的算法。 给定的输入特征向量x和一幅图像对应,我们希望识别这是否是一张猫的图片。因此我们想要一种算

【jvm学习笔记】内存回收与内存回收算法 就哪些地方需要回收、什么时候回收、如何回收三个问题进行分析和说明_jvm老年代什么时候回收-爱代码爱编程

目录 一、相关名词解释垃圾收集常用名词 二、哪些地方需要回收本地方法栈、虚拟机栈、程序计数器方法区Java堆 三、什么时候回收1. 内存能否被回收内存中的引用类型引用计数算法