内存分配-北邮OJ277

太阳不下山

地址：http://10.105.242.80/problem/p/277/
277 . 内存分配题目描述在操作系统中，内存分配是非常重要的工作。
已知内存空间由N个内存块组成，这些内存块从1到N编号，进行内存分配时，操作系统将选择一块大小足够的内存全部分配给请求内存的进程。例如，当进程请求10MB的内存时，操作系统必须向该进程分配一个不小于10MB的内存块。内存块不能被重复分配。
操作系统有三种基本的分配方式，分别为：
首次适应：从1号到N号内存块依次查找，直到找到第一块足够大的且未分配出去的内存块，将其分配给进程。
最佳适应：找到当前未分配出去且大小足够的内存块中最小的内存块分配给进程。
最差适应：找到当前未分配出去且大小足够的内存块中最大的内存块分配给进程。
其中，最佳适应是应用最为广泛的分配方式。现在，操作系统要依次处理M个进程的内存请求，请按照最佳适应方式分配内存，并输出相应分配到的内存块的大小。如果没有大小足够的内存块可以满足当前请求，则输出“NULL”（不包含引号），并跳出该请求。
输入格式输入数据的第一行是测试数据组数T（T<=50）
每组数据由4行构成：
第一行为一个整数N（1<=N<=100），表示有N个内存块。
第二行有N个整数，第i个整数表示第i块内存块的大小。
第三行为一个整数M（1<=M<=100），表示有M个请求。
第四行有M个整数，表示进程所请求的内存空间。
输出格式每组数据输出一行，每行有M个数，表示操作系统采用最佳适应方式，依次分配给进程的内存块大小；如果没有可用的内存块，输出“NULL”（不包含引号）
请不要输出多余的行尾空格，否则会被判为格式错误。
输入样例

2
4
7 5 10 3
2
4 6
4
3 5 9 10
3
5 12 6

输出样例

5 7
5 NULL 9

【分析】最佳适应算法需要对空闲块进行排序，这里放在了数组里面，使用sort函数进行排序。一般需要排序的题，我是喜欢用set的，这样可以边插入编排序。OJ的时间计算应该是在输入后吧，这样就只算最后一个数的排序了。这里可以使用multiset，删除的时候记得只删除一个，可能有重复大小的空闲块。s.erase(s.lower_bound(5))，这样就只删除集合s中的一个5了。
代码：

/*
Problem  B. 内存分配
题目描述
在操作系统中，内存分配是非常重要的工作。
已知内存空间由N个内存块组成，这些内存块从1到N编号，进行内存分配时，
操作系统将选择一块大小足够的内存全部分配给请求内存的进程。例如，当进程请求10MB的内存时，
操作系统必须向该进程分配一个不小于10MB的内存块。内存块不能被重复分配。
操作系统有三种基本的分配方式，分别为：
首次适应：从1号到N号内存块依次查找，直到找到第一块足够大的且未分配出去的内存块，将其分配给进程。
最佳适应：找到当前未分配出去且大小足够的内存块中最小的内存块分配给进程。
最差适应：找到当前未分配出去且大小足够的内存块中最大的内存块分配给进程。
其中，最佳适应是应用最为广泛的分配方式。现在，操作系统要依次处理M个进程的内存请求，
请按照最佳适应方式分配内存，并输出相应分配到的内存块的大小。
如果没有大小足够的内存块可以满足当前请求，则输出"NULL"（不包含引号），并跳出该请求。
输入格式
输入数据的第一行是测试数据组数T（T<=50）
每组数据由4行构成：
第一行为一个整数N（1<=N<=100），表示有N个内存块。
第二行有N个整数，第i个整数表示第i块内存块的大小。
第三行为一个整数M（1<=M<=100），表示有M个请求。
第四行有M个整数，表示进程所请求的内存空间。
输出格式
每组数据输出一行，每行有M个数，表示操作系统采用最佳适应方式，依次分配给进程的内存块大小；
如果没有可用的内存块，输出"NULL"（不包含引号）
请不要输出多余的行尾空格，否则会被判为格式错误。
输入样例
2
4
7 5 10 3
2
4 6
4
3 5 9 10
3
5 12 6
输出样例
5 7
5 NULL 9
Project: MemAllocation
Date:  2019/02/26
Author:  Frank Yu
*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<string>
#include<set>
#include<list>
#include<vector>
#include<map>
#include<stack>
#include<iterator>
#include<algorithm>
#include<iostream>
using namespace std;
#define F(i,m,n) for(int i=m;i<n;i++) 
//主函数
 int main()
{
int T,N,M,temp,allocation;
cin>>T;
int Mem[101];//内存空闲块 
bool flag; //可分配标志 
while(T--)
{
memset(Mem,0,sizeof(Mem));//初始化
cin>>N;//N个内存块
F(i,0,N) //输入N个空闲内存块 
{
 cin>>temp;
 Mem[i]=temp;
} 
sort(Mem+0,Mem+N);
cin>>M;
F(j,0,M)
{
  flag=false;
cin>>temp;
F(k,0,N) //从小到大遍历空闲块
{
if(temp<=Mem[k]){ //找到可分配空闲快 
cout<<Mem[k];
Mem[k]=0;//已分配置0 
flag=true;//可分配
break;
}
} 
if(!flag)
{
cout<<"NULL";
} 
if(j!=M-1)cout<<" ";//除最后一个，均输出空格 
}
cout<<endl;
}
 return 0;
}

更多数据结构与算法实现：数据结构（严蔚敏版）与算法的实现（含全部代码）
有问题请下方评论，转载请注明出处，并附有原文链接，谢谢！如有侵权，请及时联系。