文章

10

粉丝

10

获赞

2

访问

3.5k

头像
空闲块 题解(小白易懂,数组实现或结构体实现):
P1914 北京航空航天大学2021年机试题
发布于2024年8月2日 22:54
阅读数 318

####Part: 我自己写的小白易懂版

我的思路如下:

step1:建立循环单链表

step2:遍历一遍单链表,找到满足题意的最小下标节点

step3:针对这个节点做对应的空间操作:恰好相等,大于,没找到

step4:更新节点(删除,减少长度)

step5:从当前位置遍历一遍单链表,然后输出

步骤很清晰,接下来具体说说有参考意义的部分:

首先就是单链表的建立,这里当然可以用动态数组(比如vector<pair<int,int>>),但结构体会清晰很多吧

接着是遍历,有两个地方要注意:一是要存起始的位置start_index,二是要让blocks[current].length < min_length在初始的current里也满足,就要求对min_length赋一个很大的初值

空间操作没什么好说的。。。

删除节点很讲究,由于是单链表,只能循环一遍找到当前节点的上一个节点才能“越级”赋值,但是,这还并不意味着删除,记得把lenth赋值为0!不然之后输出的时候拿什么判断这个点还能不能输出呢?如果再加标志位来判断,就浪费空间了

#include <iostream>
#include <vector>
#include <climits> // 包含INT_MAX定义
#include <algorithm>

using namespace std;

struct Block 
{
    int start;   // 起始位置
    int length;  // 长度
    int next;    // 下一个节点的索引
};

int main() 
{
    int N;
    cin >> N;

    // 创建一个数组来存储所有的空闲块
    vector<Block> blocks(N);

    // 读取每个空闲块的信息
    for (int i = 0; i < N; ++i)
    {
        cin >> blocks[i].start ...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发