解题思路

1. 数据还原（字节串 → 位串）

   • 输入给出的是若干个十进制数字，每个数字是一个 byte（8 位）。

   • 每个 bit 表示一个内存单元是否空闲：

     • bit = 1 表示这个单元空闲
     • bit = 0 表示这个单元已使用

   • 题目说明「从左到右依次为编号 0~编号15」，结合示例可知：

     • 一个数字的 bit0 对应编号最低的内存单元
     • 对应顺序是：bit0, bit1, ..., bit7

   • 因此：第 i 个数字的 bit b 对应的单元编号是 i*8 + b。

   实现上：把所有字节展开成一个长度为 N = 8 * 字节数 的数组 free[]：

   free[pos] = True  表示该内存单元空闲
   free[pos] = False 表示该内存单元已使用
   

2. 在环上找到所有“连续空闲段”

   • 内存是环形的：编号 0 ~ N-1，且 0 和 N-1 相邻。

   • 先在 线性数组 free[0..N-1] 中找到所有连续为 1 的区间（段）：

     • 从左到右扫描，遇到 free[i] == 1 且前一位是 0 或 i=0，则记录一段的起点。

   • 得到若干线性段 [start, end]（闭区间）。

   • 然后处理环形拼接：

     • 如果 free[0] == 1 且 free[N-1] == 1，说明首尾是同一段，需要把第一个段和最后一个段合并成一个环形段：

       • 合并后的段起点是 last.start，终点是 first.end，表示跨越了数组尾和头。

     • 其它中间段保持不变。

   • 每个段都有一个长度 len：

     • 若不跨环（start <= end）：len = end - start + 1
     • 若跨环（start > end）：len = (N - start) + (end + 1)

3. 过滤出“长度够用”的空闲段

   • 申请长度为 k 个连续单元。
   • 对每个空闲段，如果 len >= k，说明这个段中可以找出一段长度为 k 的连续空闲单元。
   • 如果所有段都 len < k，则无法满足申请，直接输出 -1。

4. 按“长度最接近 k”筛选空闲段

   • 题目要求：在满足条件的所有空闲段中，优先选择“长度最接近申请大小”的空闲段。
   • 由于必须 len >= k，所谓“最接近”就是： 选 len 最小但仍 ≥ k 的段。
   • 扫描所有 len >= k 的段，求出最小 len_min。
   • 保留所有 len == len_min 的空闲段（可能有多个）。

5. 在这些候选段中，选“起始编号距离 m 最近”的起点

   • 在一个给定空闲段中（长度为 len_min），可以选择的起始编号 j 满足：

     • 从 j 开始的 k 个连续单元都在这个段内。

   • 对每个空闲段，我们可以把这个段在线性展开成一个数组：

     • 若不跨环：idx = [start, start+1, ..., end]
     • 若跨环：idx = [start, ..., N-1, 0, ..., end]

   • 这个展开数组长度就是该段长度 len。 能作为起点的位置是：idx[0], idx[1], ..., idx[len - k]。

   • 对每个候选起点 j，计算它与 m 的 顺时针距离：

     • 若 j > m，距离 d = j - m
     • 若 j < m，距离 d = j + N - m
     • 若 j == m，因为要求“从 m 之后开始”，跳过该起点。

   • 在所有候选空闲段的所有合法起点中，找出 距离最小 的 j，这就是答案的起始编号。

   • 若距离有并列，可以任选其一（通常选第一次出现的即可）。

6. 特殊情况处理

   • 若字节数为 0（没有内存），则直接输出 -1。

   • 若申请大小 k == 0：

     • 理论上 0 长度一定能满足，这里可约定返回 (m + 1) % N（只要有内存）。若 N = 0，则返回 -1。 （该情况题面几乎不会单独测到，但代码可安全处理。）

复杂度分析

• 设字节个数为 B，则内存单元个数 N = 8B，最大 B ≤ 500，因此 N ≤ 4000。

• 展开 bit、扫描段、枚举候选起点等操作的总量均在 O(N^2) 级别以内，但由于 N 很小，实际运算量很低。

• 时间复杂度：

  • 找段、筛选：O(N)
  • 在长度最小的段中枚举起点：最多 O(N^2)（最坏情况全空闲） 综合：O(N^2)，在约束下完全可行。

• 空间复杂度：

  • free[] 数组及若干辅助数组，规模 O(N)。 整体：O(N)。

代码实现

Python 实现

import sys

# 功能函数：根据申请大小 k、起点 m 和字节数组 data，返回起始编号
def allocate(k, m, data):
    B = len(data)
    if B == 0:
        return -1
    N = 8 * B

    # 若申请 0 个单元：约定成功，从 m+1 开始
    if k == 0:
        return (m % N + 1) % N if N > 0 else -1

    m = m % N  # 防止 m 超出范围

    # 1. 字节展开为位数组，1 表示空闲，0 表示占用
    free = [False] * N
    for i in range(B):
        val = data[i]
        for b in range(8):
            bit = (val >> b) & 1
            pos = i * 8 + b
            free[pos] = (bit == 1)

    # 2. 在线性数组中找到所有连续的 1 段
    segments = []  # 每个元素为 (start, end)，暂不考虑环
    i = 0
    while i < N:
        if free[i]:
            start = i
            j = i
            while j + 1 < N and free[j + 1]:
                j += 1
            segments.append((start, j))
            i = j + 1
        else:
            i += 1

    if not segments:
        return -1

    # 3. 处理环形连接（首尾相连）
    # 如果首尾都是 1，则把第一个段和最后一个段合并成一个跨环段
    final_segments = []
    if free[0] and free[N - 1]:
        if len(segments) == 1:
            # 整个都是 1，形成一个环形段
            s, e = segments[0]
            final_segments.append((s, e))  # 记为跨环段，用 s > e 判断
        else:
            first = segments[0]
            last = segments[-1]
            merged = (last[0], first[1])  # 起点在尾巴，终点在头部
            final_segments.append(merged)
            # 添加中间的其他段
            for seg in segments[1:-1]:
                final_segments.append(seg)
    else:
        final_segments = segments

    # 计算段的长度函数，支持跨环
    def seg_len(seg):
        s, e = seg
        if s <= e:
            return e - s + 1
        else:
            # 跨环
            return (N - s) + (e + 1)

    # 4. 过滤出长度 >= k 的段
    useful = []
    for seg in final_segments:
        length = seg_len(seg)
        if length >= k:
            useful.append((seg, length))

    if not useful:
        return -1

    # 5. 找最接近 k 的段（长度最小但 >= k）
    min_len = min(length for _, length in useful)
    candidate_segments = [seg for seg, length in useful if length == min_len]

    # 6. 在这些段中找距离 m 最近的起点
    best_start = -1
    best_dist = None

    for seg in candidate_segments:
        s, e = seg
        # 展开段上的所有下标（按顺时针顺序）
        if s <= e:
            idx_list = list(range(s, e + 1))
        else:
            # 跨环
            idx_list = list(range(s, N)) + list(range(0, e + 1))
        length = len(idx_list)

        # 能作为起点的位置：idx_list[0 .. length - k]
        for pos in range(0, length - k + 1):
            j = idx_list[pos]
            if j == m:
                continue  # 必须从 m 之后开始
            if j > m:
                dist = j - m
            else:
                dist = j + N - m

            if best_dist is None or dist < best_dist or (dist == best_dist and j < best_start):
                best_dist = dist
                best_start = j

    return best_start if best_start != -1 else -1


def main():
    # 读入所有整数
    data = list(map(int, sys.stdin.read().split()))
    if len(data) < 3:
        print(-1)
        return

    k = data[0]  # 申请的连续单元个数
    m = data[1]  # 从该编号之后开始查找
    bytes_arr = data[2:]

    ans = allocate(k, m, bytes_arr)
    print(ans)


if __name__ == "__main__":
    main()

Java 实现

import java.util.*;

/**
 * 环形内存分配问题
 */
public class Main {

    // 功能函数：根据申请大小 k、起点 m 和字节数组 data，返回起始编号
    public static int allocate(int k, int m, int[] data) {
        int B = data.length;
        if (B == 0) {
            return -1;
        }
        int N = 8 * B;

        // 申请 0 个单元的特殊处理
        if (k == 0) {
            if (N == 0) return -1;
            m = ((m % N) + N) % N;
            return (m + 1) % N;
        }

        m = ((m % N) + N) % N; // 保证在范围内

        // 1. 展开位数组
        boolean[] free = new boolean[N];
        for (int i = 0; i < B; i++) {
            int val = data[i];
            for (int b = 0; b < 8; b++) {
                int bit = (val >> b) & 1;
                int pos = i * 8 + b;
                free[pos] = (bit == 1); // 1 表示空闲
            }
        }

        // 2. 找线性连续 1 段
        List<int[]> segments = new ArrayList<int[]>(); // 每个段为 [start, end]
        int i = 0;
        while (i < N) {
            if (free[i]) {
                int start = i;
                int j = i;
                while (j + 1 < N && free[j + 1]) {
                    j++;
                }
                segments.add(new int[]{start, j});
                i = j + 1;
            } else {
                i++;
            }
        }

        if (segments.isEmpty()) {
            return -1;
        }

        // 3. 环形连接首尾
        List<int[]> finalSegments = new ArrayList<int[]>();
        if (free[0] && free[N - 1]) {
            if (segments.size() == 1) {
                // 整个为 1
                int[] seg = segments.get(0);
                finalSegments.add(new int[]{seg[0], seg[1]});
            } else {
                int[] first = segments.get(0);
                int[] last = segments.get(segments.size() - 1);
                // 合并为跨环段 [last.start, first.end]
                finalSegments.add(new int[]{last[0], first[1]});
                // 中间的其余段
                for (int idx = 1; idx < segments.size() - 1; idx++) {
                    finalSegments.add(segments.get(idx));
                }
            }
        } else {
            finalSegments = segments;
        }

        // 计算段长度的函数
        final int NN = N;
        List<int[]> useful = new ArrayList<int[]>(); // 每项 [start, end, length]

        for (int[] seg : finalSegments) {
            int s = seg[0];
            int e = seg[1];
            int len;
            if (s <= e) {
                len = e - s + 1;
            } else {
                // 跨环
                len = (NN - s) + (e + 1);
            }
            if (len >= k) {
                useful.add(new int[]{s, e, len});
            }
        }

        if (useful.isEmpty()) {
            return -1;
        }

        // 4. 找长度最小但 >= k 的段
        int minLen = Integer.MAX_VALUE;
        for (int[] seg : useful) {
            if (seg[2] < minLen) {
                minLen = seg[2];
            }
        }

        // 5. 在这些长度 == minLen 的段中，找距离 m 最近的起点
        int bestStart = -1;
        int bestDist = -1;

        for (int[] seg : useful) {
            int s = seg[0];
            int e = seg[1];
            int len = seg[2];
            if (len != minLen) continue;

            // 展开段上的所有下标
            List<Integer> idxList = new ArrayList<Integer>();
            if (s <= e) {
                for (int x = s; x <= e; x++) {
                    idxList.add(x);
                }
            } else {
                for (int x = s; x < NN; x++) {
                    idxList.add(x);
                }
                for (int x = 0; x <= e; x++) {
                    idxList.add(x);
                }
            }

            int size = idxList.size();
            for (int pos = 0; pos <= size - k; pos++) {
                int j = idxList.get(pos);
                if (j == m) continue; // 必须从 m 之后开始

                int dist;
                if (j > m) {
                    dist = j - m;
                } else {
                    dist = j + NN - m;
                }

                if (bestStart == -1 || dist < bestDist || (dist == bestDist && j < bestStart)) {
                    bestDist = dist;
                    bestStart = j;
                }
            }
        }

        return bestStart;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        List<Integer> all = new ArrayList<Integer>();
        while (sc.hasNextInt()) {
            all.add(sc.nextInt());
        }
        sc.close();

        if (all.size() < 3) {
            System.out.println(-1);
            return;
        }

        int k = all.get(0); // 申请单元数
        int m = all.get(1); // 起点 m
        int[] bytesArr = new int[all.size() - 2];
        for (int i = 2; i < all.size(); i++) {
            bytesArr[i - 2] = all.get(i);
        }

        int ans = allocate(k, m, bytesArr);
        System.out.println(ans);
    }
}

C++ 实现

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

// 功能函数：根据申请大小 k、起点 m 和字节数组 data，返回起始编号
int allocate(int k, int m, const vector<int>& data) {
    int B = (int)data.size();
    if (B == 0) return -1;
    int N = 8 * B;

    if (k == 0) {
        if (N == 0) return -1;
        m = ((m % N) + N) % N;
        return (m + 1) % N;
    }

    m = ((m % N) + N) % N;  // 防止越界

    // 1. 展开为位数组
    vector<bool> free(N, false);
    for (int i = 0; i < B; ++i) {
        int val = data[i];
        for (int b = 0; b < 8; ++b) {
            int bit = (val >> b) & 1;
            int pos = i * 8 + b;
            free[pos] = (bit == 1); // 1 表示空闲
        }
    }

    // 2. 找线性连续 1 段
    vector<pair<int, int> > segments; // [start, end]
    int i = 0;
    while (i < N) {
        if (free[i]) {
            int start = i;
            int j = i;
            while (j + 1 < N && free[j + 1]) {
                ++j;
            }
            segments.push_back(make_pair(start, j));
            i = j + 1;
        } else {
            ++i;
        }
    }

    if (segments.empty()) return -1;

    // 3. 环形连接首尾
    vector<pair<int, int> > finalSegments;
    if (free[0] && free[N - 1]) {
        if (segments.size() == 1) {
            // 整体为 1
            finalSegments.push_back(segments[0]);
        } else {
            pair<int, int> first = segments.front();
            pair<int, int> last = segments.back();
            // 合并为 [last.start, first.end]
            finalSegments.push_back(make_pair(last.first, first.second));
            for (size_t idx = 1; idx + 1 < segments.size(); ++idx) {
                finalSegments.push_back(segments[idx]);
            }
        }
    } else {
        finalSegments = segments;
    }

    // 4. 过滤 len >= k 的段
    struct SegInfo {
        int s, e, len;
    };
    vector<SegInfo> useful;
    for (size_t idx = 0; idx < finalSegments.size(); ++idx) {
        int s = finalSegments[idx].first;
        int e = finalSegments[idx].second;
        int len;
        if (s <= e) {
            len = e - s + 1;
        } else {
            len = (N - s) + (e + 1);
        }
        if (len >= k) {
            SegInfo info;
            info.s = s;
            info.e = e;
            info.len = len;
            useful.push_back(info);
        }
    }

    if (useful.empty()) return -1;

    // 5. 找最小长度
    int minLen = INT_MAX;
    for (size_t idx = 0; idx < useful.size(); ++idx) {
        if (useful[idx].len < minLen) {
            minLen = useful[idx].len;
        }
    }

    // 6. 在长度 == minLen 的段中，找距离 m 最近的起点
    int bestStart = -1;
    int bestDist = -1;

    for (size_t idx = 0; idx < useful.size(); ++idx) {
        if (useful[idx].len != minLen) continue;
        int s = useful[idx].s;
        int e = useful[idx].e;
        int len = useful[idx].len;

        vector<int> idxList;
        if (s <= e) {
            for (int x = s; x <= e; ++x) {
                idxList.push_back(x);
            }
        } else {
            for (int x = s; x < N; ++x) {
                idxList.push_back(x);
            }
            for (int x = 0; x <= e; ++x) {
                idxList.push_back(x);
            }
        }

        int size = (int)idxList.size();
        for (int pos = 0; pos <= size - k; ++pos) {
            int j = idxList[pos];
            if (j == m) continue; // 必须在 m 之后
            int dist;
            if (j > m) {
                dist = j - m;
            } else {
                dist = j + N - m;
            }

            if (bestStart == -1 || dist < bestDist || (dist == bestDist && j < bestStart)) {
                bestDist = dist;
                bestStart = j;
            }
        }
    }

    return bestStart;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<int> all;
    int x;
    while (cin >> x) {
        all.push_back(x);
    }
    if (all.size() < 3) {
        cout << -1 << "\n";
        return 0;
    }

    int k = all[0]; // 申请长度
    int m = all[1]; // 起点 m
    vector<int> bytesArr;
    for (size_t i = 2; i < all.size(); ++i) {
        bytesArr.push_back(all[i]);
    }

    int ans = allocate(k, m, bytesArr);
    cout << ans << "\n";
    return 0;
}

题目内容

有一个由若干个连续的内存单元组成的一个环形的内存块，我们现在需要从这个内存块中某个内存单元后申请指定大小的连续内存。

为了方便描述我们进行以下约定：

1. 我们用一个$10$进制byte数字序列来描述这个内存块的现状；其中每一个数字为$1$个$byte$，表示内存块中$8$个连续的内存单元，它的每一个$bit$的值用于描述$1$个内存单元是否使用，$bit$为$0$时表示内存已使用，$1$表示空闲。

2. 我们对环形内存块的每一个内存单元进行编号，假设数字序列共有$n$个数字，数字序列的第$1$个数的$bit0$到$bit7$，依次对应编号为$0$~$7$的内存单元；第$2$个数的$bit0$到$bit7$依次对应编号为8~15的内存单元，依次类推。第n个数字对应$8n-8$~$8n-1$的内存单元。从$0$到$8n-1$编号的内存单元按照物理上连续，编号越大，内存单元越高。编号$0$和$8n-1$的两个首尾内存单元相邻构成环状的内存。

现在需要在这个连续的内存块中的指定编号为$m$的内存单元之后（顺时针），找到长度为k的连续未使用的内存块，按以下规则优先进行匹配：

1. 查找方向是从$[m+1, 8n-1]$和$[0, m]$回环次序查找满足条件的连续未使用的内存单元段。

2. 当有多个内存段满足条件时，优先在大小最接近申请大小连续内存段中，申请起始编号距离$m$最近的内存段。

3. 编号距离计算方式如下：

$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$。

样例1

输入

3 6
59 143

输出

15 

说明

样例的目的是从状态为11011100 11110001（从左到右依次为编号0~编号15的内存单元使用状态）内存块中

从编号为6的内存单元后申请3个连续的内存单元。

经扫描找出3个内存段满足这点，分别为：

1. 编号8到编号11有4个内存单元

2. 编号15到编号1有3个内存单元

3. 编号3到编号5有3个内存单元

其长度最匹配的段是第2段和第3段，在这里面距离编号为6的距离分别是：

第3段：距离为9

第2段：距离为3+16-6=13

最匹配的是第2段，在其内申请3的内存单元，起始地址为15。

样例2

输入

3 1
6 17

输出

8

说明

本样例的目的是从状态为10111100 11110000（从左到右依次为编号0~编号15的内存单元使用状态）内存块中

申请3个连续的内存单元，从编号为1的内存单元后开始进行申请。

经过查找有2个内存段满足这点，分别为：

1. 编号2到编号5有4个内存单元

2. 编号8到编号10有3个内存单元

其中长度最匹配的是第2段，在这里面距离编号为1的内存单元最近的内存段是8~10，因此结果为8。

样例3

输入

3 1
0 0

输出

-1

说明

本样例的目的是从状态为00000000 00000000（从左到右依次为编号0~编号15的内存单元使用状态）内存块中

申请3个连续的内存单元，从编号为1的内存单元后开始进行申请。

经过查找没有一个连续内存块有3个连续未使用内存单元，因此结果为-1。

样例4

输入

2 1
0 254

输出

9

说明

本样例的目的是从状态为 00000000 01111111 （从左到右依次为编号 0~编号15 的内存单元(用 0 表示空) 内存块中

申请 2 个连续的内存单元。从编号为 1 的内存单元后开始进行申请。

经过计算，只有 1 个连续的空内存块：从编号 9 到编号 15。可以申请 2 个连续未使用的内存单元。这里面编号为 10 的内存单元最近的内存是 9~10。因此结果为 9

提示

可能 m 的大小小于内存单元的个数，此时返回 1，在失败场景下，返回 -1