数组模拟循环链表

5073. 空闲块 - AcWing题库

数组模拟循环链表

/*从当前位置开始遍历空闲块链表（初始是从地址最小的第一个空闲块开始），寻找满足条件的最小块
（即：大于等于请求空间的最小空闲块，如果有多个大小相同的最小空闲块，则选择遍历遇到的第一个最小空闲块）
（最佳适应原则）；
如果选择的空闲块恰好与请求的大小相符合，则将它从链表中移除并返回给用户；
这时当前位置变为移除的空闲块指向的下一空闲块；
如果选择的空闲块大于所申请的空间大小，则将大小合适的空闲块返回给用户，
剩下的部分留在空闲块链表中；这时当前位置仍然为该空闲块；
如果找不到足够大的空闲块，则申请失败；这时当前位置不变。*/
#include<iostream>
#include<cstring>
using namespace std;
const int N = 110,MAX_=1e9 + 10;
int num[N],sz[N];int n;int main(){int req;scanf("%d",&n);for(int i = 1; i <= n; i++){scanf("%d%d",&num[i],&sz[i]);}//数组模拟，判别为空，sz和是0int pt=1;while(scanf("%d",&req),req!=-1){//找min和min_iint min_=MAX_,min_i;for(int i = pt; i <= n; i++){if(!sz[i])continue;//跳过空节点if(sz[i] >= req && sz[i]<min_){min_=sz[i],min_i=i;}}for(int i = 1; i < pt; i++){if(!sz[i])continue;//跳过空节点if(sz[i] >= req && sz[i]<min_){min_=sz[i],min_i=i;}}//min_和min_i如果min_大于if(min_==MAX_)continue;else {//更新节点并更新ptif(req==sz[min_i]){sz[min_i]=0;pt=min_i+1;//下一个if(pt==n+1){pt=1;while(sz[pt]==0)pt++;}}else if(req<sz[min_i]){sz[min_i]=sz[min_i]-req;pt=min_i;}}}for(int i = pt; i <= n; i++){if(!sz[i])continue;//跳过空节点printf("%d %d\n",num[i],sz[i]);}for(int i = 1; i < pt; i++){if(!sz[i])continue;//跳过空节点printf("%d %d\n",num[i],sz[i]);}return 0;
}