洛谷 U140358 操作系统

洛谷 U140358 操作系统

洛谷传送门

题目描述

操作系统(Operating SystemOperating Syste**m，简称OSO**S)是管理计算机硬件与软件资源的计算机程序。操作系统需要处理如管理与配置内存、决定系统资源供需的优先次序、控制输入设备与输出设备、操作网络与管理文件系统等基本事务。操作系统也提供一个让用户与系统交互的操作界面。

操作系统主要包括以下几个方面的功能 ：

①进程管理，其工作主要是进程调度，在单用户单任务的情况下，处理器仅为一个用户的一个任务所独占， 进程管理的工作十分简单。但在多道程序或多用户的情况 下，组织多个作业或任务时，就要解决处理器的调度、 分配和回收等问题 。

②存储管理分为几种功能：存储分配、存储共享、存储保护 、存储扩张。

③设备管理分有以下功能：设备分配、设备传输控制 、设备独立性。

④文件管理：文件存储空间的管理、目录管理 、文件操作管理、文件保护。

⑤作业管理是负责处理用户提交的任何要求。

现在，SeawaySeawa**y自己尝试着开发了一套操作系统Seaway-AndrSeawa**y−And**r。但是由于SeawaySeawa**y水平有限，其上述部分功能并没有完善，其中bug最多的就是其内存管理系统。

在SeawaySeawa**y的开发计划里，Seaway-AndrSeawa**y−And**r的第一版内存管理系统是这样的：

1、new n：在内存中分配nn字节的空间。此命令将返回已分配的内存块的编号xx。

在SeawaySeawa**y的开发计划中，对new操作的说明是这样的：

操作newnew有一个参数nn，表示需要分配nn字节大小的内存块。在执行这个操作时，系统将把一块最靠近内存起点的，长度为nn的连续空闲字节分配到一个内存块（这块内存块内的所有字节将被标记为“已使用”）。这个操作的返回值为这块内存块的编号。如果没有符合条件的内存块，返回NULLNUL**L。

2、delete x：释放编号为xx的内存块。

在SeawaySeawa**y的开发计划中，对delete操作的说明是这样的：

操作deletedelet**e有一个参数xx，表示需要释放的内存块的编号。它将释放这个内存块（这块内存块内的所有字节将被标记为“空闲”）。如果成功释放，不返回值；如果编号为xx的内存块不存在，返回ILLEGAL_DELETE_ARGUMENTILLEGALDELET**EARGUMEN**T。

3、zhengli：碎片整理，将所有内存块全部向内存的起点靠拢并且不改变它们的顺序。

在SeawaySeawa**y的开发计划中，对zhengli操作的说明是这样的：

操作zhenglizhengli没有任何参数。它只是将所有内存块向前依次（编号小的地方）挪动直到它们紧挨在一起。**（不改变它们的顺序） **

可以看出，这个内存管理系统是简单线性的。在这个内存管理系统中，整个内存条有mm个字节，依次从1-m1−m编号。

那么，现在SeawaySeawa**y许下了丰厚的报酬（本题100pts100pts）来请你做他的内存管理系统测试员。这是你的工作指南：

你将用连续的正整数（1,2,...）作为每一个内存块的编号。比如，第ii次分配的内存块编号为ii。你的任务是：依次输出所有new指令的返回值，以及所有执行失败的delete指令的返回值。

输入格式

从文件system.insyste**m.i**n中读入数据。

第一行包括两个正整数tt和mm。tt表示操作次数，mm表示内存大小。接下来的tt行为每一次的命令。命令有以下三种，格式均由题目描述所示：new命令，后接一个整数nn；delete命令，后接一个整数xx；zhengli命令。

输出格式

输出到文件system.outsyste**m.out中。

每一行依次为每次执行的new函数的返回值或执行失败的delete函数返回的ILLEGAL_DELETE_ARGUMENTILLEGALDELET**EARGUMEN**T。

---

命题背景：

为了防爆破改了单词，因为原来的单词百度一搜就能爆出来。

---

题解：

作为本场考试的送分题，其实还是有一些难度的。

但是考虑到就是大模拟，有手就能打，数据范围小，咋维护都能过。就算每次操作从头到尾扫一遍也没有问题。

什么数据结构都没必要。

代码：

#include<cstdio>
#include<map>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
int t,m;
int v[110],cnt;
char opt[100];
bool flag;
int x;
struct node
{
	int be,en,id;
}q[110];
bool cmp(node a,node b)
{
	return a.be<b.be;
}
map<int,node> mp;
vector<node> vec;
int main()
{
	scanf("%d%d",&t,&m);
	while(t--)
	{
		scanf("%s",opt+1);
		if(opt[1]=='n')
		{
			scanf("%d",&x);
			for(int i=1;i<=m;i++)
			{
				flag=0;
				if(!v[i])
				{
					int tmp=0;
					for(int j=i;j<=m;j++)
					{
						if(!v[j])
							tmp++;
						else
							break;
						if(tmp==x)
						{
							flag=1;
							break;
						}
					}
					if(flag)
					{
						q[++cnt].be=i,q[cnt].en=i+x-1,q[cnt].id=cnt;
						for(int j=i;j<=i+x-1;j++)
							v[j]=cnt;
						mp[cnt]=q[cnt];
						printf("%d
",cnt);
						break;
					}
				}
			}
			if(!flag)
				puts("NULL");
		}
		else if(opt[1]=='d')
		{
			scanf("%d",&x);
			if(mp[x].be==0)
				puts("ILLEGAL_DELETE_ARGUMENT");
			else
			{
				for(int i=mp[x].be;i<=mp[x].en;i++)
					v[i]=0;
				mp[x].be=mp[x].en=mp[x].id=0;
			}
		}
		else
		{
			vec.clear();
			for(int i=1;i<=cnt;i++)
				if(mp[i].be!=0)
					vec.push_back(mp[i]);
			sort(vec.begin(),vec.end(),cmp);
			for(int i=0;i<vec.size();i++)
			{
				int len;
				if(!i)
				{
					len=vec[i].be-1;
					for(int j=vec[i].be;j<=vec[i].en;j++)
						v[j]=0;
					vec[i].be=1;
					vec[i].en-=len;
					for(int j=vec[i].be;j<=vec[i].en;j++)
						v[j]=vec[i].id;
					mp[vec[i].id]=vec[i];
				}
				else
				{
					len=vec[i].be-vec[i-1].en-1;
					for(int j=vec[i].be;j<=vec[i].en;j++)
						v[j]=0;
					vec[i].be=vec[i-1].en+1;
					vec[i].en-=len;
					for(int j=vec[i].be;j<=vec[i].en;j++)
						v[j]=vec[i].id;
					mp[vec[i].id]=vec[i];
				}
			}
		}
	}
	return 0;
}