数学问题——内存分配

知识点

• 内存块不能重复分配，用标志数组标志是否分配过
• 最佳适应算法
• 输出格式控制

未解决的疑问

• 用 sort() 函数将内存块从小到大排列无法通过

代码

/*
1. 内存块不能重复分配
2. 最佳适应算法 
*/ 

#include<iostream>
using namespace std;

int main(){
    
    int arr[105]; //接收内存块数组 
    bool flag[105]; //是否分配过 
    int T, N, M; //T 组数据 N 个内存块 M 个请求 
    cin>>T;
    
    while(T--){
        
        cin>>N;
        
        for(int i=0;i<105;i++){ //初始化 
            
            arr[i] = 0;
            flag[i] = false;
        }
        
        for(int i=0;i<N;i++){ //接收内存块大小 
            
            cin>>arr[i];
        }
        
        cin>>M;
        
        bool mark = false;
        while(M--){
            
            int req;
            int min = 100000;
            int index = -1;
            cin>>req;
            
            for(int i=0;i<N;i++){
                
                if(arr[i]-req>=0 && flag[i]==false){ //能容纳请求容量且未被使用 
                
                    int tmp = arr[i] - req;
                    if(tmp < min){ //找到最合适内存块 
                        
                        min = tmp;
                        index = i;
                    }
                }
            }
            
            if(index == -1){ //没有能容纳的内存块
                
                if(mark == false){
                    
                    mark = true;
                    cout<<"NULL";
                }
                else    cout<<" NULL";
            }
            else{ //有能容纳的内存块
                
                if(mark == false){
                    
                    mark = true;
                    flag[index] = true;
                    cout<<arr[index];
                } 
                else{
                
                    flag[index] = true;
                    cout<<" "<<arr[index];
                }
            }
        }
        
        cout<<endl; 
    }
    
    return 0; 
}