题面描述：

题目要求实现一个简易的内存池管理器。输入包含两行，第一行为内存池资源列表，格式为“粒度大小:数量”，不同粒度用逗号分隔；第二行为用户的内存申请列表，申请的内存大小用逗号分隔。程序需要按照先后顺序处理内存申请，优先分配粒度最小且大于等于申请量的内存，若有可用内存则分配，成功则返回true，否则返回false。输出为一个布尔列表，表示每次申请是否成功。

思路

将所有资源按照大小和数量存起来并按照大小升序排列，对于每一个申请优先找第一个大于等于它的资源可以做到最优，二分查找即可

题解分析

1. 输入处理：

   • 读取内存资源和内存申请的列表。每个资源的大小和数量通过逗号分隔的字符串输入，存入二维向量（vector<vector<int>>）中，其中每个元素保存了资源的大小和对应的数量。

2. 内存资源排序：

   • 为了能够高效地找到最适合的内存粒度，首先将内存资源按照粒度的大小进行升序排序。

3. 二分查找：

   • 在处理每个内存申请时，通过二分查找来快速找到第一个大于等于申请量的内存粒度。二分查找的复杂度为$O(\log n)$，使得查找效率很高。

4. 分配和更新资源：

   • 如果找到符合条件的内存粒度，就进行分配，并将对应的数量减一。如果某个粒度的内存数量为零，就从资源列表中删除该粒度。
   • 如果没有找到合适的内存粒度，返回false表示分配失败。

5. 输出结果：

   • 每次分配结果以true或false的形式输出，按照题目要求，用逗号分隔各个申请的结果。
   • 整体时间复杂度为$O(m \log n)$，其中$m$为申请次数，$n$为内存粒度数量。

c++

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

// 比较函数，用于对内存资源按照大小升序排列
bool cmp(vector<int> a, vector<int> b) {
    return a[0] < b[0];
}

// 二分查找，寻找第一个大于等于申请量res的内存粒度
int get(vector<vector<int>> temp, int res) {
    int l = 0, r = temp.size() - 1;
    while (l <= r) {
        int mid = l + r >> 1;
        int ans = temp[mid][0]; // 当前的内存粒度大小
        if (ans > res) {
            r = mid - 1; // 如果粒度大于申请量，向左找
        } else if (ans < res) {
            l = mid + 1; // 如果粒度小于申请量，向右找
        } else {
            return mid; // 找到正好等于申请量的粒度，返回其索引
        }
    }
    return l; // 返回第一个大于等于申请量的粒度
}

signed main() {
    // 处理输入的内存资源信息，使用二维向量存储每个粒度及其数量
    int size, cnt;
    char c;
    vector<vector<int>> v; // 存储每个内存粒度及其数量
    while (cin >> size) {
        getchar(); // 跳过冒号
        cin >> cnt; // 读取数量
        v.emplace_back(vector<int>{size, cnt}); // 存入每个资源的大小和数量
        if (getchar() != ',') break; // 如果没有逗号，说明输入结束
    }

    // 处理输入的内存申请列表
    vector<int> num; // 存储每个申请的内存大小
    while (cin >> size) {
        num.push_back(size); // 记录申请大小
        if (getchar() != ',') break; // 如果没有逗号，说明输入结束
    }

    // 将内存资源按照大小升序排列
    sort(v.begin(), v.end(), cmp);

    // 遍历每个申请，进行内存分配
    for (int i = 0; i < num.size(); i++) {
        // 使用二分查找寻找第一个大于等于申请量的内存粒度
        int j = get(v, num[i]);
        if (j < v.size()) { // 如果找到合适的内存粒度
            cout << "true";
            if (--v[j][1] == 0) { // 分配后减少数量，如果数量为0，删除该粒度
                v.erase(v.begin() + j);
            }
        } else { // 如果没有找到合适的内存粒度
            cout << "false";
        }
        if (i < num.size() - 1) cout << ","; // 输出格式：用逗号分隔
    }
}

python

# 二分查找，寻找第一个大于等于申请量res的内存粒度
def get(temp, res):
    l, r = 0, len(temp) - 1
    while l <= r:
        mid = (l + r) // 2
        ans = temp[mid][0]  # 当前的内存粒度大小
        if ans > res:
            r = mid - 1  # 如果粒度大于申请量，向左找
        elif ans < res:
            l = mid + 1  # 如果粒度小于申请量，向右找
        else:
            return mid  # 找到正好等于申请量的粒度，返回其索引
    return l  # 返回第一个大于等于申请量的粒度

# 比较函数，用于对内存资源按照大小升序排列
def cmp(a):
    return a[0]

def main():
    # 处理输入的内存资源信息
    v = []
    resources = input().split(",")  # 先按逗号分隔内存资源
    for resource in resources:
        size, cnt = map(int, resource.split(":"))  # 分别读取粒度大小和数量
        v.append([size, cnt])

    # 处理输入的内存申请列表
    num = list(map(int, input().split(",")))  # 存储每个申请的内存大小

    # 将内存资源按照大小升序排列
    v.sort(key=cmp)

    # 遍历每个申请，进行内存分配
    result = []
    for i in range(len(num)):
        # 使用二分查找寻找第一个大于等于申请量的内存粒度
        j = get(v, num[i])
        if j < len(v):  # 如果找到合适的内存粒度
            result.append("true")
            v[j][1] -= 1  # 分配后减少数量
            if v[j][1] == 0:  # 如果数量为0，删除该粒度
                v.pop(j)
        else:  # 如果没有找到合适的内存粒度
            result.append("false")

    # 输出结果，使用逗号分隔
    print(",".join(result))

# 调用主函数
if __name__ == "__main__":
    main()

java

import java.util.*;

public class Main {  // 改为Main类
    
    // 二分查找，寻找第一个大于等于申请量res的内存粒度
    public static int get(List<int[]> temp, int res) {
        int l = 0, r = temp.size() - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            int ans = temp.get(mid)[0]; // 当前的内存粒度大小
            if (ans > res) {
                r = mid - 1; // 如果粒度大于申请量，向左找
            } else if (ans < res) {
                l = mid + 1; // 如果粒度小于申请量，向右找
            } else {
                return mid; // 找到正好等于申请量的粒度，返回其索引
            }
        }
        return l; // 返回第一个大于等于申请量的粒度
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 处理输入的内存资源信息
        List<int[]> v = new ArrayList<>();
        String[] resources = scanner.nextLine().split(",");  // 先按逗号分隔内存资源
        for (String resource : resources) {
            String[] parts = resource.split(":");
            int size = Integer.parseInt(parts[0]);
            int cnt = Integer.parseInt(parts[1]);
            v.add(new int[]{size, cnt});
        }

        // 处理输入的内存申请列表
        String[] numStr = scanner.nextLine().split(",");
        int[] num = new int[numStr.length];
        for (int i = 0; i < numStr.length; i++) {
            num[i] = Integer.parseInt(numStr[i]);
        }

        // 将内存资源按照大小升序排列
        Collections.sort(v, Comparator.comparingInt(a -> a[0]));

        // 遍历每个申请，进行内存分配
        List<String> result = new ArrayList<>();
        for (int i = 0; i < num.length; i++) {
            // 使用二分查找寻找第一个大于等于申请量的内存粒度
            int j = get(v, num[i]);
            if (j < v.size()) { // 如果找到合适的内存粒度
                result.add("true");
                v.get(j)[1]--;  // 分配后减少数量
                if (v.get(j)[1] == 0) {  // 如果数量为0，删除该粒度
                    v.remove(j);
                }
            } else { // 如果没有找到合适的内存粒度
                result.add("false");
            }
        }

        // 输出结果，使用逗号分隔
        System.out.println(String.join(",", result));

        scanner.close();
    }
}

题目描述

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

分配规则如下：

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

注意：不考虑内存释放

输入描述

输入为两行字符串

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

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

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

• 申请列表不大于$100000$

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

输出描述

输出为内存池分配结果

如$true,true,true,false,false$

样例1

输入

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

输出

true,true,true,false,false

说明

内存池资源包含：$64K$共$2$个、$128K$共$1$个、$32K$共$4$个、$1K$共$128$个的内存资源；

针对$50,36,64,128,127$的内存申请序列，分配的内存依次是：$64,64,128,NULL,NULL$,

第三次申请内存时已经将$128$分配出去，因此输出结果是：

$true,true,true,false,false$