第323场周赛-第三题

给你一个整数 n ，表示下标从 0 开始的内存数组的大小。所有内存单元开始都是空闲的。

请你设计一个具备以下功能的内存分配器：

分配 一块大小为 size 的连续空闲内存单元并赋 id mID 。
释放 给定 id mID 对应的所有内存单元。
注意：

多个块可以被分配到同一个 mID 。
你必须释放 mID 对应的所有内存单元，即便这些内存单元被分配在不同的块中。
实现 Allocator 类：

Allocator(int n) 使用一个大小为 n 的内存数组初始化 Allocator 对象。
int allocate(int size, int mID) 找出大小为 size 个连续空闲内存单元且位于  最左侧 的块，分配并赋 id mID 。返回块的第一个下标。如果不存在这样的块，返回 -1 。
int free(int mID) 释放 id mID 对应的所有内存单元。返回释放的内存单元数目。
 

示例：

输入
["Allocator", "allocate", "allocate", "allocate", "free", "allocate", "allocate", "allocate", "free", "allocate", "free"]
[[10], [1, 1], [1, 2], [1, 3], [2], [3, 4], [1, 1], [1, 1], [1], [10, 2], [7]]
输出
[null, 0, 1, 2, 1, 3, 1, 6, 3, -1, 0]

解释
Allocator loc = new Allocator(10); // 初始化一个大小为 10 的内存数组，所有内存单元都是空闲的。
loc.allocate(1, 1); // 最左侧的块的第一个下标是 0 。内存数组变为 [1, , , , , , , , , ]。返回 0 。
loc.allocate(1, 2); // 最左侧的块的第一个下标是 1 。内存数组变为 [1,2, , , , , , , , ]。返回 1 。
loc.allocate(1, 3); // 最左侧的块的第一个下标是 2 。内存数组变为 [1,2,3, , , , , , , ]。返回 2 。
loc.free(2); // 释放 mID 为 2 的所有内存单元。内存数组变为 [1, ,3, , , , , , , ] 。返回 1 ，因为只有 1 个 mID 为 2 的内存单元。
loc.allocate(3, 4); // 最左侧的块的第一个下标是 3 。内存数组变为 [1, ,3,4,4,4, , , , ]。返回 3 。
loc.allocate(1, 1); // 最左侧的块的第一个下标是 1 。内存数组变为 [1,1,3,4,4,4, , , , ]。返回 1 。
loc.allocate(1, 1); // 最左侧的块的第一个下标是 6 。内存数组变为 [1,1,3,4,4,4,1, , , ]。返回 6 。
loc.free(1); // 释放 mID 为 1 的所有内存单元。内存数组变为 [ , ,3,4,4,4, , , , ] 。返回 3 ，因为有 3 个 mID 为 1 的内存单元。
loc.allocate(10, 2); // 无法找出长度为 10 个连续空闲内存单元的空闲块，所有返回 -1 。
loc.free(7); // 释放 mID 为 7 的所有内存单元。内存数组保持原状，因为不存在 mID 为 7 的内存单元。返回 0 。
 

提示：

1 <= n, size, mID <= 1000
最多调用 allocate 和 free 方法 1000 次

思路:用结构体存下每个mID,本题数据量较小,极限数据规模约10^6,实际考察了OS中内存管理的首次适应算法.考虑一个只包含0,1(分别代表内存的占用和空闲)的树状数组,通过检查下标为[x,y]的前缀和是否等于size来判断是否可以插入,这样可以把查找首次适应的区间从n优化为logn,但是树状数组的修改需要nlogn的时间开销,所以会在更新内存状态时性能略差,本方法在更大的数据量下会表现优异

class Allocator {
    int tree[5005] = {0};
    int maxa = 0;
    struct node//存下mID的结构体
    {
        int mid = 0;
        vector<int> a;//该mID的内存占用记录表
        node(int mid)
        {
            this->mid = mid;
        }
    };
vector<node> e;
int lowbit(int x){//树状数组模板
return x&-x;
}
void add(int x,int k)
{
    for(int i=x;i<=maxa;i+=lowbit(i))
    {
        tree[i]+=k;
    }
}
int find1(int x)
{
    int sum=0;
    for(int i=x;i;i-=lowbit(i))
    {
        sum+=tree[i];
    }
    return sum;
}
public:
    Allocator(int n) {
     maxa = n;
     for(int i =1;i<=1005;i++)//结构体初始化
     {
        e.push_back(node(i));
     }
     for(int i = 1;i<=n;i++)//初始设置内存全部空闲,用时nlogn
     {
        add(i,1);
     }
    }
    int allocate(int size, int mID) {
      int flag =-1;
      for(int i = 1;i<=maxa;i++)//循环检测大小为size为空闲区域,用时nlogn
      {
         if(find1(i+size-1)-find1(i-1)==size)
         {
            flag = i-1;
            for(int j = i;j<=i+size-1;j++)
            {
                e[mID].a.push_back(j);//存到该mID下的内存表中
                add(j,-1);//更新树状数组
            }
            break;
         }
      }
    return flag;
    }
    int free(int mID) {
    int p = e[mID].a.size();
      for(int i = 0;i<p;i++)
      {
          add(e[mID].a[i],1);//试放内存
      }
        e[mID].a.clear();//结构体清空
        return p;
    }
};

/**
 * Your Allocator object will be instantiated and called as such:
 * Allocator* obj = new Allocator(n);
 * int param_1 = obj->allocate(size,mID);
 * int param_2 = obj->free(mID);
 */