数据还原(字节串 → 位串)
输入给出的是若干个十进制数字,每个数字是一个 byte(8 位)。
每个 bit 表示一个内存单元是否空闲:
有一个由若干个连续的内存单元组成的一个环形的内存块,我们现在需要从这个内存块中某个内存单元后申请指定大小的连续内存。
为了方便描述我们进行以下约定:
我们用一个10进制byte数字序列来描述这个内存块的现状;其中每一个数字为1个byte,表示内存块中8个连续的内存单元,它的每一个bit的值用于描述1个内存单元是否使用,bit为0时表示内存已使用,1表示空闲。
我们对环形内存块的每一个内存单元进行编号,假设数字序列共有n个数字,数字序列的第1个数的bit0到bit7,依次对应编号为0~7的内存单元;第2个数的bit0到bit7依次对应编号为8~15的内存单元,依次类推。第n个数字对应8n−8~8n−1的内存单元。从0到8n−1编号的内存单元按照物理上连续,编号越大,内存单元越高。编号0和8n−1的两个首尾内存单元相邻构成环状的内存。
现在需要在这个连续的内存块中的指定编号为m的内存单元之后(顺时针),找到长度为k的连续未使用的内存块,按以下规则优先进行匹配:
查找方向是从[m+1,8n−1]和[0,m]回环次序查找满足条件的连续未使用的内存单元段。
当有多个内存段满足条件时,优先在大小最接近申请大小连续内存段中,申请起始编号距离m最近的内存段。
编号距离计算方式如下:
j>m时,距离j−m
j<m时,距离j+8n−m
输入是一个字符串数字序列,至少包括2行:
第1行有两个数字:第1个数字:申请的连续单元个数n,范围:0~65535
第2个数字:m,在这个编号的内存单元后开始查找,范围:0~3600;
从第2行开始为描述内存块的数字序列(可能存在换行符)。数字之间可用空格或者换行隔开,最多500个数字,每个数字范围是0~255。
比如输入:
1 2
128 64
表示在bit序列(编号0~15)为10000000 10000000(从左到右对应编号低到高)的内存块中,从编号为2的内存单元(第2个bit)后申请1个内存单元。
输出申请满足申请的内存段的起始内存单元编号。
如果不存在满足的内存段,输出−1。
输入
3 6
59 143
输出
15
说明
样例的目的是从状态为11011100 11110001(从左到右依次为编号0~编号15的内存单元使用状态)内存块中
从编号为6的内存单元后申请3个连续的内存单元。
经扫描找出3个内存段满足这点,分别为:
编号8到编号11有4个内存单元
编号15到编号1有3个内存单元
编号3到编号5有3个内存单元
其长度最匹配的段是第2段和第3段,在这里面距离编号为6的距离分别是:
第3段:距离为9
第2段:距离为3+16-6=13
最匹配的是第2段,在其内申请3的内存单元,起始地址为15。
输入
3 1
6 17
输出
8
说明
本样例的目的是从状态为10111100 11110000(从左到右依次为编号0~编号15的内存单元使用状态)内存块中
申请3个连续的内存单元,从编号为1的内存单元后开始进行申请。
经过查找有2个内存段满足这点,分别为:
编号2到编号5有4个内存单元
编号8到编号10有3个内存单元
其中长度最匹配的是第2段,在这里面距离编号为1的内存单元最近的内存段是8~10,因此结果为8。
输入
3 1
0 0
输出
-1
说明
本样例的目的是从状态为00000000 00000000(从左到右依次为编号0~编号15的内存单元使用状态)内存块中
申请3个连续的内存单元,从编号为1的内存单元后开始进行申请。
经过查找没有一个连续内存块有3个连续未使用内存单元,因此结果为-1。
输入
2 1
0 254
输出
9
说明
本样例的目的是从状态为 00000000 01111111 (从左到右依次为编号 0~编号15 的内存单元(用 0 表示空) 内存块中
申请 2 个连续的内存单元。从编号为 1 的内存单元后开始进行申请。
经过计算,只有 1 个连续的空内存块:从编号 9 到编号 15。可以申请 2 个连续未使用的内存单元。这里面编号为 10 的内存单元最近的内存是 9~10。因此结果为 9
提示
可能 m 的大小小于内存单元的个数,此时返回 1,在失败场景下,返回 -1