星环

题目分析

环形空间站上有若干仓库,状态由字节序列描述:每个字节的二进制位表示 8 个连续仓库的状态(1 = 空闲,0 = 占用)。仓库首尾相连形成环。货船在位置 ,需要 个连续空闲仓库停靠,按以下优先级分配:

  1. 最佳适配:在所有长度 的空闲段中,选择长度最接近 的(即长度差最小的)。
  2. 最近优先:长度差相同时,选择距离 最近的段。距离按环形顺时针方向计算:若段起点 ,距离为 ;否则距离为 (绕一圈)。

思路

环形空闲段枚举 + 贪心选择

  1. 解码字节序列:将每个字节展开为 8 个二进制位,第 个字节的第 位对应仓库
  1. 提取连续空闲段:线性扫描找出所有极大连续空闲段。由于仓库是环形的,如果第一个段从仓库 0 开始、最后一个段延伸到仓库 ,则需要将它们合并为一个跨越首尾的环形段。
  1. 贪心匹配:遍历所有长度 的空闲段,按"长度差最小 距离最近"的优先级选出最优段,返回其起始位置。若无满足条件的段,返回

代码

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

int main() {
    int k, m;
    scanf("%d%d", &k, &m);
    vector<int> bytes;
    int b;
    while (scanf("%d", &b) == 1) bytes.push_back(b);

    int total = bytes.size() * 8;
    vector<int> idle(total);
    for (int i = 0; i < (int)bytes.size(); i++)
        for (int j = 0; j < 8; j++)
            idle[i * 8 + j] = (bytes[i] >> j) & 1;

    struct Seg { int start, len; };
    vector<Seg> segs;
    int i = 0;
    while (i < total) {
        if (idle[i]) {
            int j = i;
            while (j < total && idle[j]) j++;
            segs.push_back({i, j - i});
            i = j;
        } else i++;
    }
    // 环形合并:首尾段相连
    if (segs.size() >= 2 && segs.front().start == 0
        && segs.back().start + segs.back().len == total) {
        segs.back().len += segs.front().len;
        segs.erase(segs.begin());
    }

    int bestFit = -1, bestDist = -1, bestStart = -1;
    for (auto& seg : segs) {
        if (seg.len < k) continue;
        int fit = seg.len - k;
        int s = seg.start;
        int dist = s > m ? s - m : total - m + s;
        if (s == m) dist = total;
        if (bestFit == -1 || fit < bestFit || (fit == bestFit && dist < bestDist)) {
            bestFit = fit;
            bestDist = dist;
            bestStart = s;
        }
    }
    printf("%d\n", bestStart);
    return 0;
}
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt(), m = sc.nextInt();
        List<Integer> bytes = new ArrayList<>();
        while (sc.hasNextInt()) bytes.add(sc.nextInt());

        int total = bytes.size() * 8;
        int[] idle = new int[total];
        for (int i = 0; i < bytes.size(); i++)
            for (int j = 0; j < 8; j++)
                idle[i * 8 + j] = (bytes.get(i) >> j) & 1;

        List<int[]> segs = new ArrayList<>();
        int i = 0;
        while (i < total) {
            if (idle[i] == 1) {
                int j = i;
                while (j < total && idle[j] == 1) j++;
                segs.add(new int[]{i, j - i});
                i = j;
            } else i++;
        }
        if (segs.size() >= 2 && segs.get(0)[0] == 0
                && segs.get(segs.size() - 1)[0] + segs.get(segs.size() - 1)[1] == total) {
            segs.get(segs.size() - 1)[1] += segs.get(0)[1];
            segs.remove(0);
        }

        int bestFit = -1, bestDist = -1, bestStart = -1;
        for (int[] seg : segs) {
            if (seg[1] < k) continue;
            int fit = seg[1] - k;
            int s = seg[0];
            int dist = s > m ? s - m : total - m + s;
            if (s == m) dist = total;
            if (bestFit == -1 || fit < bestFit || (fit == bestFit && dist < bestDist)) {
                bestFit = fit;
                bestDist = dist;
                bestStart = s;
            }
        }
        System.out.println(bestStart);
    }
}
import sys

def main():
    data = sys.stdin.read().split()
    idx = 0
    k = int(data[idx]); idx += 1
    m = int(data[idx]); idx += 1
    bytes_list = []
    while idx < len(data):
        bytes_list.append(int(data[idx])); idx += 1

    total = len(bytes_list) * 8
    idle = [0] * total
    for i, b in enumerate(bytes_list):
        for j in range(8):
            idle[i * 8 + j] = (b >> j) & 1

    segs = []
    i = 0
    while i < total:
        if idle[i]:
            j = i
            while j < total and idle[j]:
                j += 1
            segs.append([i, j - i])
            i = j
        else:
            i += 1

    if len(segs) >= 2 and segs[0][0] == 0 and segs[-1][0] + segs[-1][1] == total:
        segs[-1][1] += segs[0][1]
        segs.pop(0)

    best_fit = best_dist = best_start = -1
    for start, length in segs:
        if length < k:
            continue
        fit = length - k
        dist = start - m if start > m else total - m + start
        if start == m:
            dist = total
        if best_fit == -1 or fit < best_fit or (fit == best_fit and dist < best_dist):
            best_fit = fit
            best_dist = dist
            best_start = start

    print(best_start)

main()
const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    const data = lines.join(' ').split(/\s+/).map(Number);
    let idx = 0;
    const k = data[idx++], m = data[idx++];
    const bytes = [];
    while (idx < data.length) bytes.push(data[idx++]);

    const total = bytes.length * 8;
    const idle = new Array(total).fill(0);
    for (let i = 0; i < bytes.length; i++)
        for (let j = 0; j < 8; j++)
            idle[i * 8 + j] = (bytes[i] >> j) & 1;

    const segs = [];
    let i = 0;
    while (i < total) {
        if (idle[i]) {
            let j = i;
            while (j < total && idle[j]) j++;
            segs.push([i, j - i]);
            i = j;
        } else i++;
    }
    if (segs.length >= 2 && segs[0][0] === 0
        && segs[segs.length - 1][0] + segs[segs.length - 1][1] === total) {
        segs[segs.length - 1][1] += segs[0][1];
        segs.shift();
    }

    let bestFit = -1, bestDist = -1, bestStart = -1;
    for (const [s, len] of segs) {
        if (len < k) continue;
        const fit = len - k;
        let dist = s > m ? s - m : total - m + s;
        if (s === m) dist = total;
        if (bestFit === -1 || fit < bestFit || (fit === bestFit && dist < bestDist)) {
            bestFit = fit;
            bestDist = dist;
            bestStart = s;
        }
    }
    console.log(bestStart);
});

复杂度分析

  • 时间复杂度,其中 为仓库总数(字节数 ,最多 )。解码、扫描空闲段、遍历选择均为线性。
  • 空间复杂度,存储每个仓库的空闲状态和空闲段列表。