AcWing 5073. 空闲块
原题链接
中等
作者:
ober02
,
2024-03-27 20:47:57
,
所有人可见
,
阅读 2
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int n; // 链表长度
int h, e[N],w[N], ne[N], be[N], idx; // w:容量
int find(int del) // 找到最佳适应点
{
int res = h, minv = 1e9 , cnt = n;
for(int i = h; cnt-- ; i = ne[i])
{
int vol = w[i];
if(vol < minv && vol >= del){
minv = vol;
res = i;
}
}
if(minv < 1e9 ) return res;
else return -1; // 没找到
}
void dt(int x) //删除x节点
{
ne[be[x]] = ne[x];
be[ne[x]] = be[x];
h = ne[x];
n--;
}
int main()
{
cin >> n;
for(int i = 0; i< n ;i++){
int node, v;
scanf("%d%d", &node, &v);
e[idx] = node, w[idx] = v, ne[idx] = idx+1, be[idx] = idx-1 , idx++;
}
be[0] = n-1, ne[n-1] = 0; // 循环链表
int del;
while(cin >> del && del != -1)
{
int dnode = find(del);
if(dnode != -1){
w[dnode] = w[dnode] - del;
h = dnode;
if(w[dnode] == 0) dt(dnode);//删除
}
}
for(int i = h; n--; i = ne[i])
{
cout << e[i] <<" " << w[i] << endl;
}
}