REALHW96 星环

题目链接

星环

题目描述

在一个环形空间站上，资源仓呈线性排列且首尾相连。我们需要为一艘货船寻找一段长度至少为 的连续空闲资源仓。

状态表示: 空间站的状态由一个十进制 byte 序列描述。序列中每个数字代表一个“监控单元”，对应 8 个连续的资源仓。该数字的二进制表示中的每一位 (bit) 描述了一个资源仓的状态：1 代表“空闲”，0 代表“已被占用”。 资源仓从 0 开始统一编号。若监控单元序列有 个数字，则总仓位为 。第 个数字（0-indexed）的 bit 0 到 bit 7 对应 到 号资源仓。

分配规则: 从货船当前停靠的 号资源仓开始，顺时针寻找一片长度至少为 的连续空闲资源仓。分配时需遵循以下优先级规则：

  1. 最优匹配 (Best-Fit): 如果找到多个满足长度要求的连续空闲仓段，优先选择长度最接近 的仓段。
  2. 最近原则 (Nearest-First): 在所有“最优匹配”的仓段中，选择起始编号离 距离最近的一个。
  3. 距离计算: 设候选仓段的起始编号为 ，总仓位数为 。
    • 若 ，距离为 。
    • 若 ，距离为 （回环距离）。

任务目标: 输出最终分配的资源仓段的起始编号。如果无法找到，则输出 -1。

解题思路

本题的核心是正确地解码空间站状态，并严格按照“最优匹配”和“最近原则”两级优先级对所有可能的停靠方案进行筛选。

步骤 1: 解码状态，构建环形阵列

首先，我们需要将输入的 byte 序列转换为一个单一的、能直观表示所有资源仓状态的布尔（或0/1）数组。

  • 设输入的 byte 序列有 个数字，则资源仓总数 。
  • 创建一个大小为 的数组 bays。
  • 遍历输入的每个 byte 值 B。对于 B 的二进制表示中的每一位 j (从 0 到 7)，其状态 (B >> j) & 1 对应 bays 数组中相应位置的状态。第 i 个 byte 值 B_i 对应 bays 数组的 [8*i, 8*i+7] 区间。

步骤 2: 搜寻所有可行的连续空闲段

完成解码后，我们需要遍历 bays 数组，找出所有长度大于等于 的连续空闲段。

  • 为了处理环形结构，一个巧妙的方法是在遍历到数组末尾时，能无缝地回到数组开头。这可以通过取模运算 % N 实现。
  • 我们遍历 bays 数组，当遇到一个空闲仓 bays[i] == 1，且其前一个仓位 bays[(i - 1 + N) % N] 被占用 == 0 时，说明我们找到了一个新空闲段的起点。
  • 从这个起点开始，继续向后（环形地）遍历，直到遇到一个被占用的仓位，从而计算出该连续空闲段的完整长度。
  • 如果该段的长度大于等于 ，就将其作为一个候选方案，以 (起始位置, 长度) 的形式记录下来。

步骤 3: 依据规则进行多级筛选

在找到所有候选方案后，我们按优先级进行筛选：

  1. 最优匹配 (Best-Fit):

    • 在所有候选方案中，找到一个最小的长度 min_len，这个长度必须大于等于 。
    • 筛选出所有长度等于 min_len 的方案，进入下一轮筛选。

  2. 最近原则 (Nearest-First):

    • 对于上一轮筛选出的所有“最优”长度的方案，我们需要计算每一个方案的起始位置 到给定位置 的“环形距离”。
    • 一个简洁的距离计算公式是 distance = (s - m + N) % N，它统一了 和 两种情况。
    • 在这些方案中，选择距离最小的一个。

步骤 4: 输出结果

  • 经过两轮筛选后，最终剩下的唯一方案的起始位置就是我们的答案。
  • 如果在步骤 2 中没有找到任何长度大于等于 的空闲段，则说明无法满足要求，输出 -1。

代码

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <climits>

using namespace std;

// 候选方案结构体
struct Candidate {
    int start;
    int length;
};

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

    int k, m;
    cin >> k >> m;

    vector<int> bays;
    int byte_val;
    // 读取所有 byte 值
    while (cin >> byte_val) {
        // 将每个 byte 解码为 8 个仓位状态
        for (int i = 0; i < 8; ++i) {
            bays.push_back((byte_val >> i) & 1);
        }
    }

    if (bays.empty()) {
        cout << -1 << endl;
        return 0;
    }
    
    int n = bays.size();

    // 步骤 2: 搜寻所有候选段
    vector<Candidate> candidates;
    for (int i = 0; i < n; ++i) {
        // 寻找一个空闲段的起点 (当前为空闲，前一个为占用)
        if (bays[i] == 1 && bays[(i - 1 + n) % n] == 0) {
            int start_idx = i;
            int current_len = 0;
            int j = i;
            // 计算该空闲段的长度
            while (bays[j % n] == 1) {
                current_len++;
                j++;
                // 如果整个环都是空闲的，避免死循环
                if (j % n == start_idx) break;
            }
            if (current_len >= k) {
                candidates.push_back({start_idx, current_len});
            }
        }
    }

    if (candidates.empty()) {
        cout << -1 << endl;
        return 0;
    }

    // 步骤 3.1: 最优匹配筛选
    int best_len = INT_MAX;
    for (const auto& cand : candidates) {
        best_len = min(best_len, cand.length);
    }
    
    vector<Candidate> best_fit_candidates;
    for (const auto& cand : candidates) {
        if (cand.length == best_len) {
            best_fit_candidates.push_back(cand);
        }
    }

    // 步骤 3.2: 最近原则筛选
    int min_dist = INT_MAX;
    int final_start = -1;

    for (const auto& cand : best_fit_candidates) {
        // 计算环形距离
        int dist = (cand.start - m + n) % n;
        if (dist < min_dist) {
            min_dist = dist;
            final_start = cand.start;
        }
    }

    cout << final_start << endl;

    return 0;
}

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    // 候选方案类
    static class Candidate {
        int start;
        int length;

        Candidate(int start, int length) {
            this.start = start;
            this.length = length;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        int m = sc.nextInt();

        List<Integer> bays = new ArrayList<>();
        // 读取所有 byte 值
        while (sc.hasNextInt()) {
            int byteVal = sc.nextInt();
            // 将每个 byte 解码为 8 个仓位状态
            for (int i = 0; i < 8; i++) {
                bays.add((byteVal >> i) & 1);
            }
        }

        if (bays.isEmpty()) {
            System.out.println(-1);
            return;
        }

        int n = bays.size();

        // 步骤 2: 搜寻所有候选段
        List<Candidate> candidates = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            // 寻找一个空闲段的起点 (当前为空闲，前一个为占用)
            if (bays.get(i) == 1 && bays.get((i - 1 + n) % n) == 0) {
                int startIdx = i;
                int currentLen = 0;
                int j = i;
                // 计算该空闲段的长度
                while (bays.get(j % n) == 1) {
                    currentLen++;
                    j++;
                    // 如果整个环都是空闲的，避免死循环
                    if (j % n == startIdx) break;
                }
                if (currentLen >= k) {
                    candidates.add(new Candidate(startIdx, currentLen));
                }
            }
        }

        if (candidates.isEmpty()) {
            System.out.println(-1);
            return;
        }

        // 步骤 3.1: 最优匹配筛选
        int bestLen = Integer.MAX_VALUE;
        for (Candidate cand : candidates) {
            bestLen = Math.min(bestLen, cand.length);
        }
        
        List<Candidate> bestFitCandidates = new ArrayList<>();
        for (Candidate cand : candidates) {
            if (cand.length == bestLen) {
                bestFitCandidates.add(cand);
            }
        }

        // 步骤 3.2: 最近原则筛选
        int minDist = Integer.MAX_VALUE;
        int finalStart = -1;

        for (Candidate cand : bestFitCandidates) {
            // 计算环形距离
            int dist = (cand.start - m + n) % n;
            if (dist < minDist) {
                minDist = dist;
                finalStart = cand.start;
            }
        }

        System.out.println(finalStart);
    }
}

import sys

def solve():
    # 读取第一行
    k, m = map(int, input().split())

    bays = []
    # 读取剩余的所有 byte 值
    remaining_input = sys.stdin.read()
    parts = remaining_input.split()

    for part in parts:
        if part:
            byte_val = int(part)
            # 将每个 byte 解码为 8 个仓位状态
            for i in range(8):
                bays.append((byte_val >> i) & 1)
    
    if not bays:
        print(-1)
        return

    n = len(bays)
    
    # 步骤 2: 搜寻所有候选段
    candidates = []
    for i in range(n):
        # 寻找一个空闲段的起点 (当前为空闲，前一个为占用)
        if bays[i] == 1 and bays[(i - 1 + n) % n] == 0:
            start_idx = i
            current_len = 0
            j = i
            # 计算该空闲段的长度
            while bays[j % n] == 1:
                current_len += 1
                j += 1
                # 如果整个环都是空闲的，避免死循环
                if j % n == start_idx:
                    break
            
            if current_len >= k:
                candidates.append({'start': start_idx, 'length': current_len})

    if not candidates:
        print(-1)
        return

    # 步骤 3.1: 最优匹配筛选
    best_len = min(cand['length'] for cand in candidates)
    best_fit_candidates = [cand for cand in candidates if cand['length'] == best_len]

    # 步骤 3.2: 最近原则筛选
    min_dist = float('inf')
    final_start = -1

    for cand in best_fit_candidates:
        # 计算环形距离
        dist = (cand['start'] - m + n) % n
        if dist < min_dist:
            min_dist = dist
            final_start = cand['start']
            
    print(final_start)

solve()

算法及复杂度

  • 算法: 模拟, 贪心筛选
  • 时间复杂度: , 其中 是资源仓的总数。
    • 解码输入、构建 bays 数组的时间复杂度为 。
    • 遍历数组以寻找所有候选段的时间复杂度为 。
    • 对候选段进行两轮筛选的时间复杂度与候选段数量成正比，最坏情况下为 。
    • 因此，总时间复杂度为 。
  • 空间复杂度:
    • 需要 的空间来存储 bays 数组。
    • 存储候选段列表也需要最多 的空间。
    • 因此，总空间复杂度为 。