刷题笔记合集🔗

内存资源分配

问题描述

有一个简易内存池，内存按照大小粒度分类，每个粒度有若干个可用内存资源，用户会进行一系列内存申请，需要按需分配内存池中的资源返回申请结果成功失败列表。

分配规则如下：

1. 分配的内存要大于等于内存的申请量，存在满足需求的内存就必须分配，优先分配粒度小的，但内存不能拆分使用；
2. 需要按申请顺序分配，先申请的先分配，有可用内存分配则申请结果为 true；
3. 没有可用则返回 false。

注意：不考虑内存释放

输入格式

输入为两行字符串

第一行为内存池资源列表，包含内存粒度数据信息，粒度数据间用逗号分割

• 一个粒度信息内用冒号分割，冒号前为内存粒度大小，冒号后为数量
• 资源列表不大于
• 每个粒度的数量不大于

第二行为申请列表，申请的内存大小间用逗号分割

• 申请列表不大于

输出格式

输出为内存池分配结果，结果用逗号分隔。

样例输入

64:2,128:1,32:4,1:128
50,36,64,128,127

样例输出

true,true,true,false,false

数据范围

• 资源列表不大于
• 每个粒度的数量不大于
• 申请列表不大于

题解

这道题考察的是模拟内存分配过程，关键在于理解分配规则，特别是"优先分配粒度小的"这一要求。

解题思路：

1. 首先将内存池按照粒度大小进行排序（升序），这样我们可以优先分配粒度小的内存。
2. 对于每个内存申请，在排序后的内存池中找到第一个大于等于申请大小的内存块。
3. 如果找到了合适的内存块，分配它并标记结果为true；如果未找到，标记结果为false。

一个关键优化点是使用二分查找来加速寻找合适内存块的过程。这是因为：

• 资源列表可能长达1024个不同粒度
• 申请列表可能长达100000个申请

如果对每个申请都线性遍历内存池，时间复杂度会达到O(1024 * 100000)，这可能导致超时。而使用二分查找，可以将查找内存块的时间复杂度从O(n)降低到O(log n)，整体时间复杂度降低到O(m * log n)，其中m是申请列表的长度，n是内存池的长度。

在实现上，我们可以维护两个数组：一个保存内存粒度大小，另一个保存对应的可用数量。这样当某个粒度的内存用完时，可以方便地从数组中移除。

算法的时间复杂度是O(m * log n)，其中m是申请列表的长度，n是内存池的长度。在最坏情况下，这是O(100000 * log 1024)，这个复杂度对于给定的数据范围是可以接受的。

参考代码

• Python

import sys  
input = lambda:sys.stdin.readline().strip()  

# 输入处理
pools_str = input()
applies_str = input()

# 解析内存池
pools = []
for item in pools_str.split(','):
    if ':' in item:
        size, count = map(int, item.split(':'))
        pools.append([size, count])

# 解析申请列表
applies = []
for item in applies_str.split(','):
    try:
        applies.append(int(item))
    except:
        # 处理异常输入，如空格
        pass

# 二分查找函数
def bin_search(sizes, target):
    """二分查找找到第一个>=target的位置"""
    l, r = 0, len(sizes) - 1
    while l <= r:
        mid = (l + r) // 2
        if sizes[mid] < target:
            l = mid + 1
        elif sizes[mid] > target:
            r = mid - 1
        else:
            return mid
    return l if l < len(sizes) else -1

# 主要处理逻辑
def proc_mem(pools, applies):
    # 按内存大小升序排序
    pools.sort(key=lambda x: x[0])
    
    # 分离出大小和数量数组便于操作
    mem_sizes = []
    mem_counts = []
    for s, c in pools:
        mem_sizes.append(s)
        mem_counts.append(c)
    
    res = []
    for req in applies:
        # 找到首个>=req的内存块
        idx = bin_search(mem_sizes, req)
        
        # 内存分配失败的情况
        if idx == -1 or idx >= len(mem_sizes):
            res.append("false")
            continue
        
        # 分配内存
        mem_counts[idx] -= 1
        res.append("true")
        
        # 如果该大小内存用完了，从列表中移除
        if mem_counts[idx] == 0:
            mem_sizes.pop(idx)
            mem_counts.pop(idx)
    
    return ','.join(res)

print(proc_mem(pools, applies))

• Cpp

#include <bits/stdc++.h>
using namespace std;

// 二分查找函数
int bin_find(const vector<int>& sizes, int key) {
    int left = 0;
    int right = sizes.size() - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (sizes[mid] < key) {
            left = mid + 1;
        } else if (sizes[mid] > key) {
            right = mid - 1;
        } else {