#6WA,求调(代码带注释)

CF7B Memory Manager

IOI_official @ 2023-12-23 09:48:56

#include<bits/stdc++.h>
using namespace std;
int t,m,n,ii=1,jj,kk,ks,js,a[105],bb,ss,jjj=1,cc,iii;//这一大坨变量会在程序中解释 
bool ff[114514],fff,ffff;//ff数组为调试用,ff[i]相当于h[i].f 
struct node{
    bool f;//此字节有没有被占 
    int b,s;//b是此字节所属内存块的编号,s是此内存块的字节数量 
};
node h[100005];//内存条数组 
string g;//操作 
int main(){
    scanf("%d%d",&t,&m);
    for(int i=1;i<=t;i++){
        cin>>g;
        if(g!="defragment")
            cin>>n;//如果操作不是defragment,就在后面再输入一个数字 
        if(g=="alloc"){
            for(int j=1;j<=m;j++){
                cc=0;//cc是内存条中连续空闲空间的长度 
                for(int k=j;k<=m;k++){
                    if(h[k].f==0){
                        cc++;
                        if(k==j){
                            ii=k;//ii是这段连续空闲空间的首地址 
                        }
                    }
                    else break;//连续空闲空间中断就退出 
                }
                if(cc>=n){
                    break;//如果这个连续空闲空间可以让要分配的内存长度插进去的话,就退出,将要分配的内存块插进此连续空闲空间中 
                }
            }
            if(cc<n){
                cout<<"NULL"<<'\n';//如果内存条中没有够用的空间让要分配的内存块插就输出NULL 
                continue;//退出 
            }
            if(ii+n-1>iii){
                iii=ii+n;//iii是最后一个内存块的末尾地址+1 
            }
            jj++;//jj是此内存块的编号 
            for(int j=ii;j<=ii+n-1;j++){
                h[j].f=1;//将此字节标记为被占用 
                ff[j]=1;
                h[j].b=jj;
            }//从连续空闲空间的首地址一直循环n次 
            a[jj]=n;//此数组是用来存每个内存块的长度的 
            cout<<jj<<'\n';//输出编号 
            ss+=a[jj];//内存条中被占用的字节的数量 
        }
        if(g=="erase"){
            ffff=0;//标记 
            if(n<=0||n>jj){
                cout<<"ILLEGAL_ERASE_ARGUMENT"<<'\n';
                continue;
            }//如果给的编号越界,就输出ILLEGAL_ERASE_ARGUMENT,然后退出 
            for(int j=1;j<=m;j++){
                if(h[j].b==n){//如果找到了要删除的内存块 
                    if(h[j].f==0){
                        cout<<"ILLEGAL_ERASE_ARGUMENT"<<'\n';
                        ffff=1;
                        break;
                    }//如果这个编号已经被删除过了,就输出ILLEGAL_ERASE_ARGUMENT,将标记变为1,退出 
                    h[j].f=0;//如果没被删除过,就将它删除 
                    ff[j]=0;
                }
            }
            if(ffff==1)continue;//如果有标记,跳出
            ss-=a[n];
            if(n==jj){
                iii=ss-a[n]+1;//总数-最靠近内存条末尾内存块的长度+1 
            }//如果删的是最靠近内存条末尾的内存块,就更改最ii的值(最后一个内存块的末尾地址+1) 
            a[n]=0;//将此内存块的长度变为0 
        }
        if(g=="defragment"){
            for(int k=1;k<=m;k++){
                for(int j=1;j<=m;j++){
                    if(h[j].f==0&&ks==0&&iii>j){
                        ks=j;//ks为向左移最多能移到哪 
                        continue;
                    }//如果此字节未被占用,且ks没值,且当前字节在最靠末尾的被占用的字节的前面 
                    if(h[j].f==1&&ks!=0){
                        js=j;//js是要被移动的内存块的左端点的位置 
                        bb=h[j].b;//bb是要被移动的内存块的长度 
                        break;//找到后退出 
                    }
                }
                if(ks!=0&&js!=0){//如果ks和js都不为空 
                    for(int j=js;j<=a[bb]+js-1;j++){//循环从js开始,循环要移动的内存块的长度次 
                        h[j].f=0;//将此字节变为0 
                        ff[j]=0;
                        h[ks+j-js].f=1;//ks+j-js是这个字节要移动到的地址 
                        ff[ks+j-js]=1;
                    }
                    iii=ss+1;//整理完后ii会变成总数+1 
                }
                ks=0;//ks归0 
            }
        }
    }
    return 0;
}

|