2014.计算机下午.Problem B. 内存分配

亦凉 2023-07-18 06:23 87阅读 0赞

**题目描述**  
在操作系统中，内存分配是非常重要的工作。  
已知内存空间由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

#include<bits/stdc++.h>
    using namespace std;
    const int maxn=105;
    int main() { 
    	int T,n,m,need;
    	cin>>T;
    	while(T--) { 
    		cin>>n;
    		int a[maxn],c[maxn];
    		for(int i=0; i<n; i++) { 
    			cin>>a[i];
    			c[i]=0;//记录是否被分配 
    		}
    		sort(a,a+n);
    		cin>>m;
    		for(int i=0; i<m; i++) { 
    			cin>>need;
    			int flag=0,tmp;
    			if(i!=0) { 
    				cout<<" ";
    			}
    			for(int j=0; j<n; j++) { 
    				if(a[j]>=need&&c[j]==0) { 
    					flag=1;
    					c[j]=1;
    					cout<<a[j];
    					break;
    				}
    			}
    			if(flag==0) { 
    				cout<<"NULL";
    			}
    		}
    		cout<<endl;
    	}
    }