星环
题目分析
环形空间站上有若干仓库,状态由字节序列描述:每个字节的二进制位表示 8 个连续仓库的状态(1 = 空闲,0 = 占用)。仓库首尾相连形成环。货船在位置 ,需要
个连续空闲仓库停靠,按以下优先级分配:
- 最佳适配:在所有长度
的空闲段中,选择长度最接近
的(即长度差最小的)。
- 最近优先:长度差相同时,选择距离
最近的段。距离按环形顺时针方向计算:若段起点
,距离为
;否则距离为
(绕一圈)。
思路
环形空闲段枚举 + 贪心选择
- 解码字节序列:将每个字节展开为 8 个二进制位,第
个字节的第
位对应仓库
。
- 提取连续空闲段:线性扫描找出所有极大连续空闲段。由于仓库是环形的,如果第一个段从仓库 0 开始、最后一个段延伸到仓库
,则需要将它们合并为一个跨越首尾的环形段。
- 贪心匹配:遍历所有长度
的空闲段,按"长度差最小
距离最近"的优先级选出最优段,返回其起始位置。若无满足条件的段,返回
。
代码
#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);
});
复杂度分析
- 时间复杂度:
,其中
为仓库总数(字节数
,最多
)。解码、扫描空闲段、遍历选择均为线性。
- 空间复杂度:
,存储每个仓库的空闲状态和空闲段列表。

京公网安备 11010502036488号