Yuzhen's Blog

Yuzhen Qin

题解:P5763 [NOI1999] 内存分配

10
2024-06-17

题意

N 个内存单元。

\le10^4 个进程,每个进程有三个整数 T,M,P数据已按 T 从小到大排序T,M,P<10^9

对于一个进程,T 表示申请内存的时刻,M 表示申请内存的长度,P 表示占用内存的时间。如果当前存在长度为 M 的空内存,就分配给它,否则放入等待队列。注意,在进行内存分配处理过程中,处于等待队列队头的进程的处理优先级最高,队列中的其它进程不能先于队头进程被处理

输出全部进程运行完毕的时刻被放入过等待队列的进程总数

做法

题目中有两种操作:分配内存操作和释放内存操作。

显然,只有新的进程申请内存或者已有的进程释放内存时,才会分配新的内存。在已有的进程释放内存时只会分配给等待队列里的进程。

我们可以使用一个 std::set 来维护内存。

queue<pair<int /* 内存长度 M */, int /* 占用时间 P */> > waits;
set<pair<int /* 左端点 L */, int /* 内存长度 M */> > runs;

当出现一个新的内存申请时,遍历 runs,如果找到足够长的内存就立即分配,如果无法找到就放入 waits

bool assign(int t, int m, int p) {
    // 遍历 `runs`
    for(auto it = runs.begin(); it != runs.end(); it++) {
        // 找到下一块被分配的内存
        auto jt = it;
        jt++;

        if(jt != runs.end()) {
            // 空闲内存区间的左端点就等于
            // 前面分配了的内存区间的左端点加分配的内存长度
            int start = it -> first + it -> second;
            // 求出空闲区间的长度,如果需要分配的长度
            // 小于等于空闲区间的长度,就立即分配
            if(m <= jt -> first - start) {
                runs.insert({start, m});
                // 将分配插入到维护内存释放信息的堆里
                // 见下文
                endts.push({t + p, start});

                return true;
            }
        }
    }

    return false;
}

当新的内存申请时间是 T 时,应该释放 T T 之前释放的内存。

释放的时候应该检查能否分配给等待队列队头的内存申请。

可以使用一个堆(std::priority_queue)来维护内存释放的信息。

priority_queue<pair<int, int>,
               vector<pair<int, int> >,
               // 小根堆
               greater<pair<int, int> > > endts;

写一个函数 void release(int t),代表释放时刻 \le T 时应该释放的内存。

void release(int t) {
    // 时刻 <= T
	while(!endts.empty() && endts.top().first <= t) {
        // 同一时刻释放的内存一起释放
		int f = endts.top().first;
		while(endts.size() && endts.top().first == f) {
			auto top = endts.top();
			endts.pop();
			auto it = runs.lower_bound({top.second, 0});
			runs.erase(it);
		}

        // 记录已经运行的时间
		ans = f;

        // 考虑等待队列里的进程
		while(waits.size()) {
			auto front = waits.front();
			if(assign(f, front.first, front.second))
				waits.pop();
			else
				break;
		}
	}
}

main 函数时需要注意:

  1. 需要插入内存边界

    runs.insert({-1, 1});
    runs.insert({ n, 1});
    
  2. 等待所有内存分配请求处理完之后,应该把所有进程运行结束

    release(2e9);
    

完整代码(无注释)

#include <bits/stdc++.h>
using namespace std;

int n, cnt, t, m, p, ans;
queue<pair<int, int> > waits;
set<pair<int, int> > runs;
priority_queue<pair<int, int>,
               vector<pair<int, int> >,
			   greater<pair<int, int> > > endts;
			   
bool assign(int t, int m, int p) {
	for(auto it = runs.begin(); it != runs.end(); it++) {
		auto jt = it;
		jt++;
		if(jt != runs.end()) {
			int start = it -> first + it -> second;
			if(m <= jt -> first - start) {
				runs.insert({start, m});
				endts.push({t + p, start});
				return true;
			}
		}
	}
	return false;
}

void release(int t) {
	while(!endts.empty() && endts.top().first <= t) {
		int f = endts.top().first;
		while(endts.size() && endts.top().first == f) {
			auto top = endts.top();
			endts.pop();
			auto it = runs.lower_bound({top.second, 0});
			runs.erase(it);
		}

		ans = f;

		while(waits.size()) {
			auto front = waits.front();
			if(assign(f, front.first, front.second))
				waits.pop();
			else
				break;
		}
	}
} 

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr); 

	cin >> n;

	runs.insert({-1, 1});
	runs.insert({n, 1});

	while(cin >> t >> m >> p, t || m || p) {
		release(t);
		if(!assign(t, m, p)) {
			waits.push({m, p});
			cnt++;
		}
	}

	release(2e9);

	cout << ans << endl << cnt << endl;

	return 0;
}