刷题笔记合集🔗

问题描述

小基负责管理一个总空间为 字节的堆内存。现在，他需要从中新申请一块内存。内存分配原则为：优先紧接着前一块已使用内存，分配空间足够且最接近申请大小的空闲内存。

输入格式

第 行是 个整数，表示期望申请的内存字节数。

第 到第 行是用空格分割的两个整数，表示当前已分配的内存的情况，每一行表示一块已分配的连续内存空间，每行的第 和第 个整数分别表示偏移地址和内存块大小。

输出格式

若申请成功，输出申请到内存的偏移；若申请失败，输出 。

样例输入1

1
0 1
3 2

样例输出1

1

样例输入2

10
0 20
30 10
50 10
70 10
90 10

样例输出2

20

样例输入3

30
0 20
30 10
50 10
70 10
90 10

样例输出3

-1

样例解释

样例 解释说明

样例1	堆中已使用的两块内存是偏移从0开始的1字节和偏移从3开始的2字节，空闲的两块内存是偏移从1开始2个字节和偏移从5开始95字节，根据分配原则，新申请的内存应从1开始分配1个字节，所以输出偏移为1。
样例2	堆中已使用的内存块分别是：0-19、30-39、50-59、70-79、90-99，空闲的内存块分别是：20-29、40-49、60-69、80-89。根据分配原则，新申请10字节的内存应从20开始分配，所以输出偏移为20。
样例3	堆中最大的空闲内存块只有10字节，无法满足申请30字节的需求，所以输出-1。

数据范围

• 申请的内存大小
• 偏移地址
• 内存块大小
• 已分配内存块数量不超过

题解

这道题目要求我们在一个总大小为100字节的堆内存中，按照特定规则申请一块新的内存。

首先，我们需要理解内存分配的原则：

1. 优先紧接着前一块已使用内存
2. 分配空间足够且最接近申请大小的空闲内存

解题思路如下：

1. 首先检查申请的内存大小是否合法（大于0且不超过100）
2. 将已分配的内存块按照起始位置（偏移地址）排序
3. 遍历排序后的内存块，检查每个内存块的合法性：
   • 内存块的起始位置不应小于前一个内存块的结束位置（否则会有重叠）
   • 内存块的起始位置不应大于99
   • 内存块的大小应大于0且不超过从该位置到堆末尾的剩余空间
4. 在遍历过程中，计算每两个相邻内存块之间的空闲空间大小
5. 如果空闲空间足够大（大于等于申请的内存大小），且比之前找到的最佳空闲空间更接近申请大小，则更新最佳申请位置
6. 最后，还需要检查最后一个已分配内存块之后到堆末尾的空闲空间

时间复杂度分析：

• 对内存块排序需要 的时间
• 遍历内存块需要 的时间
• 因此，总时间复杂度为

对于给定的数据范围（内存块数量不超过100），这个复杂度是可以接受的。

参考代码

class Mem:
    def __init__(self, pos, len_val):
        """
        初始化内存块
        
        参数:
            pos: 内存块起始位置
            len_val: 内存块大小
        """
        self.pos = pos  # 内存块起始位置
        self.len = len_val  # 内存块大小


# 算法入口
def find_mem():
    """
    寻找合适的内存块
    
    返回:
        申请到的内存偏移，如果申请失败则返回-1
    """
    # 读取申请的内存大小
    req_size = int(input())
    
    # 读取已占用的内存
    used = []
    while True:
        try:
            p, s = map(int, input().split())
            used.append(Mem(p, s))
        except:
            break
    
    # 申请的内存大小非法，则返回-1
    if req_size <= 0 or req_size > 100:
        return -1
    
    # 记录最优的申请内存起始位置
    best_pos = -1
    # 记录最接近申请内存的空闲内存块大小
    min_size = 101
    
    # 对占用的内存按照起始位置升序
    used.sort(key=lambda x: x.pos)
    
    # 记录空闲内存块的起始位置
    free_pos = 0
    
    for blk in used:
        # 检查内存块是否合法
        if blk.pos < free_pos or blk.pos > 99:
            return -1
        
        if blk.len <= 0 or blk.len > 100 - blk.pos:
            return -1
        
        # 计算空闲内存块
        if blk.pos > free_pos:
            # 空闲内存块大小
            free_size = blk.pos - free_pos
            
            # 如果该空闲内存块大小足够，且最接近申请的内存大小
            if req_size <= free_size < min_size:
                best_pos = free_pos
                min_size = free_size
        
        # 更新空闲内存的起始位置
        free_pos = blk.pos + blk.len
    
    # 检查最后一个空闲内存块
    last_free = 100 - free_pos
    if req_size <= last_free < min_size:
        best_pos = free_pos
    
    return best_pos


# 主函数
if __name__ == "__main__":
    print(find_mem())

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/**
 * 内存块结构体
 */
struct Blk {
    int pos;  // 内存块起始位