#P1561. 2023.05.24-暑期实习-第一题-连续内存合并

2023.05.24-暑期实习-第一题-连续内存合并

题目描述

塔子哥最近对在开发一个简单的操作系统,今天他的任务是为操作系统的动态内存管理模块实现内存块的合并功能。

介绍一下操作系统的内存管理模块:操作系统的动态内存管理模块是操作系统中非常重要的一部分,其主要功能是在程序运行时动态地分配和释放内存。动态内存管理模块根据程序的内存需求,调用物理内存管理模块,对内存进行分配或者释放。为了使得内存的分配更加高效,动态内存管理模块通常会实现内存池的机制。内存池就是一个预先分配好一定数量的内存块的集合,程序运行时可以从内存池中获取内存块,而不必动态地去分配内存空间。这样可以极大地提高内存分配的速度。动态内存管理模块还负责内存的回收和整理。当程序不再使用某些内存空间时,动态内存管理模块将这些空间标记为可回收空间,并把它们加入内存释放队列。在适当的时候,动态内存管理模块就会回收这些空间,并重新整理内存空间,以便留出更大的连续内存块来给后续的内存分配操作使用。"

塔子哥考虑这个模块可以根据用户需求分配任意大小的内存块,并在用户释放内存时将其回收到内存池中以供其他用户使用,他把这个任务安排给了小G同学。小G同学需要设计并实现这个回收合并模块,这个模块在每次释放内存块后返回当前最大的连续内存块的起始位置和长度。如果存在多个最大连续内存块,返回起始位置最小的内存块。

输入描述

输入是一组释放的内存块编号,用逗号分隔。例如,输入 "1,3,2,51,3,2,5" 表示释放了四个内存块,它们的编号分别为 1321、3、255。每个内存块的大小为 11 个单位。请注意,函数执行前所有内存块都已被申请完毕,没有空闲内存块。不需要考虑重复释放内存块。

内存块编号: 00 \leq 编号 \leq 23112^{31} - 1

单词释放的内存块个数 \leq 1000010000

输出描述

输出是一个由两个整数组成的元组,表示经过回收处理后当前可用的最大连续内存块的起始编号和长度。例如,输出 "1,31,3" 表示合并后的连续内存块的起始编号是 11,长度为 33。如果存在多个最大连续内存块,则返回起始编号最小的那个。

样例1

输入:

2,4,3,7,6

输出

2,3

解释

2,4,3,7,62 ,4, 3, 7 ,6 表示释放了 55 块内存,内存块编号分别为 2,4,3,7,62, 4, 3 ,7, 6 .

经过回收合并后,2,3,42,3,4 三块内存连续,可以合并为一块大内存、大小为 33 个单位

6,76 ,7 两块内存连续,合并后连续内存大小为 22

因此返回此时的最大连续内存的起始位置为 22 ,内存大小为 33

样例2

输入

1,3,7,9,8,6

输出

6,4