5073. 空閑塊 - AcWing題庫

數(shù)組模擬循環(huán)鏈表

/*從當(dāng)前位置開始遍歷空閑塊鏈表（初始是從地址最小的第一個空閑塊開始），尋找滿足條件的最小塊
（即：大于等于請求空間的最小空閑塊，如果有多個大小相同的最小空閑塊，則選擇遍歷遇到的第一個最小空閑塊）
（最佳適應(yīng)原則）；
如果選擇的空閑塊恰好與請求的大小相符合，則將它從鏈表中移除并返回給用戶；
這時當(dāng)前位置變?yōu)橐瞥目臻e塊指向的下一空閑塊；
如果選擇的空閑塊大于所申請的空間大小，則將大小合適的空閑塊返回給用戶，
剩下的部分留在空閑塊鏈表中；這時當(dāng)前位置仍然為該空閑塊；
如果找不到足夠大的空閑塊，則申請失敗；這時當(dāng)前位置不變。*/
#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]);}//數(shù)組模擬，判別為空，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;//跳過空節(jié)點if(sz[i] >= req && sz[i]<min_){min_=sz[i],min_i=i;}}for(int i = 1; i < pt; i++){if(!sz[i])continue;//跳過空節(jié)點if(sz[i] >= req && sz[i]<min_){min_=sz[i],min_i=i;}}//min_和min_i如果min_大于if(min_==MAX_)continue;else {//更新節(jié)點并更新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;//跳過空節(jié)點printf("%d %d\n",num[i],sz[i]);}for(int i = 1; i < pt; i++){if(!sz[i])continue;//跳過空節(jié)點printf("%d %d\n",num[i],sz[i]);}return 0;
}