小根堆key为释放时间,值为双链表中对应节点的指针(数组下标);朴素遍历寻找首地址最小的那个空闲地址片,然后O(1)插入,且保证了有序性;删除当前时刻下释放时间最早的进程时,直接通过堆获取链表对应元素的指针(数组下标),然后O(1)删除,且保证了有序性;
// 先实现Set后,才自己尝试用链表实现的;
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 10010;
#define inf_t 1e9
int n, last_time, ans_cnt;
// --------------------------------------------------- 链表模拟内存条的声明与函数定义;
struct data_M {
int s, m; // 起始地址 内存长度
};
int l[N], r[N], idx;
data_M runs[N];
void list_init() {
runs[0].s = -1, runs[0].m = 1;
runs[1].s = n, runs[1].m = 1;
r[0] = 1, l[1] = 0;
idx = 2;
}
void list_add(int k, data_M node) {
runs[idx] = node;
l[idx] = k;
r[idx] = r[k];
l[r[k]] = idx;
r[k] = idx;
idx ++;
}
void list_remove(int k) {
l[r[k]] = l[k];
r[l[k]] = r[k];
}
// --------------------------------------------------- 等待队列声明与函数定义;
struct data_Q {
int m, p; // 内存长度 运行时间
};
int hh = 0, tt = -1;
data_Q waits[N];
// --------------------------------------------------- 小根堆声明与函数定义;
struct data_T {
int e, i; // 释放时间 链表指针
};
int c;
data_T endts[N];
void up(int p) {
while (p > 1) {
if (endts[p].e < endts[p / 2].e) {
swap(endts[p], endts[p / 2]);
p /= 2;
}
else break;
}
}
void down(int p) {
int s = p * 2;
while (s <= c) {
if (s < c && endts[s].e > endts[s + 1].e) s ++;
if (endts[p].e > endts[s].e) {
swap(endts[p], endts[s]);
p = s, s = p * 2;
}
else break;
}
}
void heap_push(data_T node) { endts[++ c] = node; up(c); }
void heap_pop() { endts[1] = endts[c --]; down(1); }
// --------------------------------------------------- 主函数(内存释放等待进程尝试唤醒 以及 内存分配 的模块);
bool assign(int t, int m, int p) {
for (int i = 0, j = r[0]; i != 1; i = j, j = r[i]) {
if (runs[j].s - (runs[i].s + runs[i].m) >= m) {
heap_push({t + p, idx});
list_add(i, {runs[i].s + runs[i].m, m});
return true;
}
}
return false;
}
void release(int cur_t) {
while (c != 0 && endts[1].e <= cur_t) {
last_time = endts[1].e;
while (c != 0 && endts[1].e == last_time) {
int del_idx = endts[1].i;
heap_pop();
list_remove(del_idx);
}
while (hh <= tt) {
data_Q top = waits[hh];
if (assign(last_time, top.m, top.p)) hh ++;
else break;
}
}
}
// --------------------------------------------------- 函数运行入口处;
int main() {
int t, m, p;
scanf("%d", &n);
list_init();
while (scanf("%d%d%d", &t, &m, &p), t || m || p) {
release(t);
if (!assign(t, m, p)) {
waits[++ tt] = {m, p};
ans_cnt ++;
}
}
release(inf_t);
printf("%d\n%d", last_time, ans_cnt);
return 0;
}
// 附上Set实现,踩了好多坑;
#include <cstdio>
#include <algorithm>
#include <set>
#include <vector>
#include <queue>
using namespace std;
struct data_M {
int s, m; // 所占内存的首地址(即起始下标) 以及 占用内存长度;
bool operator < (const data_M& t) const { return s < t.s; } // 起始地址不会重复,唯一;
}; // 作用:分配内存时线性扫描查找是否有满足条件的空闲内存块;
struct data_Q {
int m, p; // 内存长度 以及 运行时间;
}; // 作用:若刚来的进程直接得到分配则直接在当前时刻传递参数分配内存即可,
// 一旦是等待队列中的进程 其要运行,必定是开始于某个进程结束的内存释放时间,且要存储对应的内存长度与运行时间以传参;
struct data_E {
int e, s; // 释放时间 以及 所占内存的首地址(即起始下标);
}; // 作用:当新来一个进程时,释放掉所有释放时间小于当前时刻的进程所占的内存空间,每次获取最小释放时间,且需定位到进程所占的内存位置;
// 由于进程所占的起始位置是唯一的,因此作为释放时间对应的值;
struct cmp {
// 注意构建小根堆时 返回 a > b,即更大元素下浮操作返回true;
bool operator() (const data_E& a, const data_E& b) { return a.e > b.e; } // 可能重复,但不会去重;
}; // Debug了一个多小时,原来是小根堆的比较函数出现了错误!!!
int n, last_time, ans_cnt; // 存储总内存单元数、记录最早可结束的进程的时刻、记录存储至等待队列的进程数量;
set<data_M> running;
queue<data_Q> waiting;
priority_queue<data_E, vector<data_E>, cmp> endtimes;
bool assign(int t, int m, int p) {
for (auto it = running.begin(); it != -- running.end(); it ++) {
auto jt = it; jt ++;
if ((*jt).s - ((*it).s + (*it).m) >= m) {
int start_idx = (*it).s + (*it).m;
running.insert({start_idx, m});
endtimes.push({t + p, start_idx});
return true;
}
}
return false;
}
void release(int cur_t) {
// 一个Bug的调错: 循环一旦有一个进程的内存被释放,就可唤醒等待队列中的进程尝试分配内存;而非将所有的释放时间小于cur_t的进程全部释放内存后才处理;
while (endtimes.size() && endtimes.top().e <= cur_t) {
last_time = endtimes.top().e;
while (endtimes.size() && endtimes.top().e == last_time) {
int start_idx = endtimes.top().s;
endtimes.pop();
auto it = running.lower_bound({start_idx, 0});
running.erase(it);
}
while (waiting.size()) {
data_Q top = waiting.front();
if (assign(last_time, top.m, top.p))
waiting.pop();
else break;
}
}
}
int main() {
int t, m, p;
scanf("%d", &n);
running.insert({-1, 1});
running.insert({n, 1});
while (scanf("%d%d%d", &t, &m, &p), t || m || p) {
release(t);
if (!assign(t, m, p)) {
waiting.push({m, p});
ans_cnt ++;
}
}
release(1e9);
printf("%d\n%d", last_time, ans_cnt);
return 0;
}