算法描述

算法流程

本算法采用小根堆管理进程表，队列管理等待进程，实现进程调度和内存分配。

符号定义

算法步骤

1. 终止条件：
   • 所有进程已处理且进程表为空 → 算法结束
   • 否则继续执行
2. 进程处理判断：
   • 存在未处理进程 → 执行步骤3
   • 否则 → 执行步骤6
3. 进程表状态判断：
   • 进程表为空 → 执行步骤5
   • 否则 → 执行步骤4
4. 时间比较：
   • p1起始时间 < p2结束时间 → 执行步骤5
   • 否则 → 执行步骤6
5. 内存分配尝试：
   • 成功分配：
     1. 更新p1结束时间 = 开始时间 + 运行时间
     2. 加入进程表
     3. 调整堆结构
   • 分配失败：
     1. 加入等待队列
     2. count++
   • 返回步骤1
6. 进程销毁处理：
   • 更新duration = p2结束时间
   • 销毁所有结束时间=duration的进程
   • 释放内存
   • 调整堆结构
   • 执行步骤7
7. 等待队列处理：
   • 尝试为p3分配内存：
     1. 成功分配：
        • 更新p3结束时间 = duration + 运行时间
        • 加入进程表
        • 移出等待队列
        • 调整堆结构
     2. 分配失败 → 返回步骤1
   • 循环执行步骤7

数据结构

• 进程表：小根堆，按结束时间排序
• 等待队列：FIFO队列

复杂度分析

• 时间复杂度：O(nlogn)，n为进程数
• 空间复杂度：O(n)

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

const int N = 10010;
const int INF = 2e9;

struct Node
{
	int value;
	bool tag;
	Node *Prev, *Next;
};

int n, t, m, len, res, tot, w = INF;
vector<pair<int, Node*>> p;
queue<pair<int, int>> q;
Node *head, *tail;

inline void read(int &x)
{
	int sgn = 1; x = 0;
	char ch = getchar();
	while(ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
	if(ch == '-') sgn = -1, ch = getchar();
	while(ch >= '0' && ch <= '9') x = (x << 1) + (x << 3), x += (ch ^ '0'), ch = getchar();
	x *= sgn;
}

inline void insert(Node *p, int val, bool op)
{
	Node *q = new Node();
	q->value = val; q->tag = op;
	p->Next->Prev = q;
	q->Next = p->Next;
	p->Next = q; q->Prev = p;
}

inline void remove(Node *p)
{
	p->Prev->Next = p->Next;
	p->Next->Prev = p->Prev;
	delete p;
}

inline void get_blank(Node *p)
{
	int val = p->value;
	if(p->Prev != head && p->Prev->tag == 0) val += p->Prev->value, remove(p->Prev);
	if(p->Next != tail && p->Next->tag == 0) val += p->Next->value, remove(p->Next);
	Node *last = p->Prev; remove(p);
	insert(last, val, 0);
}

inline bool task_in(int t, int m, int len, int &w)
{
	for(Node *it = head->Next; it != tail; it = it->Next)
	{
		if(it->tag == 0 && it->value >= m)
		{
			int val = it->value; val -= m;
			Node *last = it->Prev; remove(it);
			insert(last, m, 1); last = last->Next;
			if(val != 0) insert(last, val, 0);
			p.push_back({t + len, last}); w = min(w, t + len);
			return true;
		}
	}
	return false;
}

inline void task_out()
{
	int wzs = INF;
	for(int i = 0; i < p.size(); i ++ )
	{
		if(p[i].first == w) get_blank(p[i].second), p.erase(p.begin() + i -- );
		else wzs = min(wzs, p[i].first);
	}
	while(!q.empty())
	{
		pair<int, int> x = q.front();
		if(!task_in(w, x.first, x.second, wzs)) break;
		q.pop();
	}
	w = wzs;
} 

int main()
{
	read(n);
	head = new Node(); tail = new Node();
	head->Next = tail; tail->Prev = head;
	insert(head, n, 0);
	while(1)
	{
		read(t); read(m); read(len);
		if(!t && !m && !len) break;
		while(t >= w) task_out();
		if(!task_in(t, m, len, w)) q.push({m, len}), tot ++ ;
	}
	while(!q.empty()) task_out();
	for(int i = 0; i < p.size(); i ++ ) w = max(w, p[i].first);
	printf("%d\n%d\n", w, tot);
	return 0;
}