模拟题9——CSP202603C. 进程通信

一、总体题意题目要求我们模拟一个操作系统中的内存分配与进程通信过程。系统拥有一段初始为空的全局内存地址从 (0) 开始。虽然内存容量达到了 (10^{100})但题目保证内存一定足够使用。系统中一共有 (n) 个进程每个进程可以建立多个接口。每个接口都会对应一个队列而每个队列需要占用一段连续的内存空间。一共有三种操作new p L为进程 (p) 创建一个容量为 (L) 的新队列send p进程 (p) 向它的所有接口分别发送一个对象delete p i删除进程 (p) 的第 (i) 个接口及其对应队列。下面分别说明这三种操作。1.new p L为进程 (p) 创建一个长度为 (L) 的新队列。分配内存时采用最优适应原则找到所有连续的未占用区间只考虑长度不小于 (L) 的区间在这些区间中选择长度最短的如果有多个长度相同的区间则选择左端点最小的从选中区间的左端点开始分配连续 (L) 个地址。操作完成后需要输出新队列的起始地址。例如当前已经占用[2,4]、[9,11]那么空闲区间为[0,1]、[5,8]、[12,∞)如果要申请长度为 (3) 的队列则会选择[5,8]并分配[5,7]输出起始地址52.send p进程 (p) 会同时向它的所有接口发送一个对象。每个接口对应的队列都可以看作一个循环队列第一次发送时写入队列起始地址之后每次向后移动一个地址到达队列末尾后下一次重新回到起始地址如果某个地址原来已经存有对象新的对象可以直接覆盖它。操作完成后需要输出本次所有对象写入地址的总和。例如某个队列占用区间[9,11]连续发送五次对象写入的位置依次为9、10、11、9、10因此不需要记录每个位置具体保存了什么对象只需要记录这个队列下一次应该写入的位置。3.delete p i删除进程 (p) 的第 (i) 个接口以及对应队列。需要完成以下操作释放该队列占用的整段内存删除队列中的所有对象将编号大于 (i) 的接口编号依次减一。例如某个进程原来拥有四个接口1号、2号、3号、4号删除第 2 个接口后剩余接口编号变成1号、2号、3号其中新的 2 号接口就是原来的 3 号接口。二、思路解析1. 为什么不能直接开内存数组题目给出的内存容量为显然不能定义一个长度为的数组。不过我们并不需要保存每个内存地址的状态。观察三种操作可以发现new只关心哪些区间已经被占用delete会直接释放一个完整区间send只关心当前队列下一次写入的位置内存中对象的具体内容不会影响后续操作。因此我们只需要记录当前所有已经被占用的内存区间每个进程拥有的队列每个队列下一次发送对象时的写入地址。这样就不需要真的建立一个巨大数组。2. 队列信息的设计每个接口对应一个队列我们为每个队列保存三个信息struct Queue { long long start; long long len; long long next; };各变量含义如下start队列在内存中的起始地址len队列长度next下一次发送对象时写入的地址。例如一个队列占用[5,7]那么start 5; len 3; next 5;第一次发送后写入地址5然后令next 6;第二次发送后写入地址6然后令next 7;第三次发送后写入地址7此时需要重新回到起始地址next 5;因此队列中的写入位置会按照下面的顺序循环5 → 6 → 7 → 5 → 6 → 7 → ...3. 保存每个进程的接口每个进程可以拥有多个接口并且接口编号从 (1) 开始。我们可以使用二维vectorvectorvectorQueue interfaces(n 1);其中interfaces[p]保存进程 (p) 的所有队列。由于vector的下标从 (0) 开始因此进程的 1 号接口对应下标0进程的 2 号接口对应下标1进程的 (i) 号接口对应下标i - 1。使用vector还有一个好处删除某个元素后后面的元素会自动向前移动正好符合题目中“后续接口重新编号”的要求。4. 保存所有已占用区间我们使用map保存当前所有已经被占用的内存区间maplong long, long long occupied;其中occupied[left] right;表示内存区间[left, right]已经被某个队列占用。之所以使用map是因为map会按照键从小到大自动排序。因此所有区间都会按照左端点从小到大排列。例如occupied[2] 4; occupied[9] 11;表示当前占用区间为[2,4]、[9,11]按照顺序扫描这些占用区间就可以计算出它们之间的空闲区间。5. 处理new操作假设当前占用区间按照左端点排序后为[l1,r1]、[l2,r2]、[l3,r3]那么有限的空闲区间为[0,l1-1] [r11,l2-1] [r21,l3-1]最后还有一个无限长的空闲区间[r31,∞)我们使用变量long long previousEnd -1;表示前一个占用区间的右端点。为什么初始值是-1因为内存从地址0开始所以第一个可能的空闲地址就是previousEnd 1 0对于当前占用区间[left, right]它和上一个占用区间之间的空闲段为long long freeStart previousEnd 1; long long freeEnd left - 1;空闲区间长度为long long freeLength freeEnd - freeStart 1;如果空闲区间长度不少于申请长度L就说明这个区间可以使用。根据最优适应原则我们记录当前找到的最短合法空闲区间if (freeLength L freeLength bestLength) { bestLength freeLength; bestStart freeStart; }这里只在freeLength严格小于bestLength时更新。当两个空闲区间长度相同时不进行更新。因为我们是从左向右扫描的先找到的区间左端点一定更小符合题目要求。完整扫描代码如下long long bestStart -1; long long bestLength LLONG_MAX; long long previousEnd -1; for (const auto [left, right] : occupied) { long long freeStart previousEnd 1; long long freeEnd left - 1; if (freeStart freeEnd) { long long freeLength freeEnd - freeStart 1; if (freeLength L freeLength bestLength) { bestLength freeLength; bestStart freeStart; } } previousEnd right; }如果扫描完所有有限空闲区间后仍然有bestStart -1说明没有合适的有限空闲区间。此时直接在最后一个占用区间后面分配bestStart previousEnd 1;因为最后一个空闲区间可以一直延伸到并且题目保证内存足够大所以一定可以完成分配。得到起始地址后新队列的结束地址为long long end bestStart L - 1;然后记录占用区间occupied[bestStart] end;并将队列加入进程 (p)interfaces[p].push_back({bestStart, L, bestStart});新队列的下一次写入地址就是它的起始地址。最后输出cout bestStart \n;6. 处理send操作执行send p时需要向进程 (p) 的每一个接口发送一个对象。遍历该进程的所有队列for (Queue que : interfaces[p]) { answer que.next; que.next; if (que.next que.start que.len) { que.next que.start; } }首先answer que.next;将本次写入地址加入答案。然后que.next;将下一次写入位置向后移动。队列最后一个地址是que.start que.len - 1因此当next变成que.start que.len时说明已经越过队列末尾需要回到队列起始地址que.next que.start;最终输出本次所有对象写入地址的总和。注意答案必须使用long long。因为单个地址可能达到几十亿而一次send可能向大量接口发送对象地址总和可能超过int的范围。7. 处理delete操作执行delete p i时接口编号 (i) 对应的vector下标为int index i - 1;先得到这个队列的起始地址long long start interfaces[p][index].start;由于occupied使用队列起始地址作为键因此可以直接释放对应区间occupied.erase(start);然后从进程 (p) 的接口数组中删除该队列interfaces[p].erase(interfaces[p].begin() index);删除之后后面的元素会自动向前移动。例如原来的接口编号为1、2、3、4删除 2 号接口之后原来的 3、4 号接口会自动变成新的 2、3 号接口完全符合题目要求。8. 为什么不需要记录对象状态题目中为每个地址定义了两个状态该地址是否被队列占用该地址是否存有对象。但在实际模拟中我们并不需要显式维护这两个数组。对于我们使用占用区间occupied代替。对于后续操作并不关心一个地址之前有没有对象再次发送时可以直接覆盖删除时会释放整个队列输出只要求本次对象写入地址的总和。因此只记录队列下一次写入的位置即可。9. 复杂度分析设当前系统中一共有 (m) 个队列。对于new操作需要扫描所有已经占用的区间时间复杂度为O(m)对于send操作需要遍历该进程的所有接口。假设该进程有 (k) 个接口时间复杂度为O(k)对于delete操作从map中删除区间的复杂度为 O(log m)从vector中删除元素最坏需要 O(m)。因此总时间复杂度最坏为O(q²)本题中所以 O(q²) 的模拟可以通过。空间复杂度为O(q)因为系统中同时存在的队列数量不会超过new操作的总数。三、总结这道题的重点并不是模拟每个内存地址而是进行抽象。虽然内存容量为但真正需要维护的只有每个队列占用的连续区间每个进程当前拥有的队列每个队列下一次写入的位置。使用map维护所有已占用区间可以按照地址顺序扫描空闲段从而实现最优适应内存分配。使用vector保存每个进程的接口可以自然处理接口的建立、遍历和删除后的重新编号。每个队列只需要记录下一次写入位置就可以实现循环写入不需要保存每个内存地址是否已经存有对象。完整代码如下#include iostream #include vector #include map #include climits #include string using namespace std; // 一个接口对应一个队列 struct Queue { long long start; // 队列起始地址 long long len; // 队列长度 long long next; // 下一次发送对象时写入的地址 }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin n q; // interfaces[p] 保存进程 p 当前拥有的所有队列 vectorvectorQueue interfaces(n 1); // occupied[left] right // 表示区间 [left, right] 已经被占用 maplong long, long long occupied; while (q--) { string operation; cin operation; if (operation new) { int p; long long L; cin p L; // 当前最优空闲区间的左端点 long long bestStart -1; // 当前最优空闲区间的长度 long long bestLength LLONG_MAX; // 上一个占用区间的右端点 long long previousEnd -1; // 按左端点从小到大扫描所有占用区间 for (const auto [left, right] : occupied) { // 上一个占用区间与当前占用区间之间的空闲段 long long freeStart previousEnd 1; long long freeEnd left - 1; if (freeStart freeEnd) { long long freeLength freeEnd - freeStart 1; // 最优适应选择长度最短的合法空闲段 // 长度相同时保留先找到的也就是左端点更小的 if (freeLength L freeLength bestLength) { bestLength freeLength; bestStart freeStart; } } previousEnd right; } // 没有合适的有限空闲段 // 使用最后面的无限空闲段 if (bestStart -1) { bestStart previousEnd 1; } long long end bestStart L - 1; // 记录新的占用区间 occupied[bestStart] end; // 新队列第一次发送时写入起始地址 interfaces[p].push_back({ bestStart, L, bestStart }); cout bestStart \n; } else if (operation send) { int p; cin p; long long answer 0; // 向进程 p 的所有接口发送一个对象 for (Queue que : interfaces[p]) { // 本次对象写入的位置 answer que.next; // 更新下一次写入位置 que.next; // 到达队列末尾后回到起始位置 if (que.next que.start que.len) { que.next que.start; } } cout answer \n; } else if (operation delete) { int p, i; cin p i; // 接口编号从 1 开始 // vector 下标从 0 开始 int index i - 1; // 找到对应队列的起始地址 long long start interfaces[p][index].start; // 释放该队列占用的内存 occupied.erase(start); // 删除接口 // 后面的接口会自动向前移动并重新编号 interfaces[p].erase( interfaces[p].begin() index ); } } return 0; }转载请注明出处