文章目錄

• 題目描述
• 解析
• 代碼

題目描述

解析

這題感覺做的不錯
不難看出，要維護一個空閑的優(yōu)先隊列，在每次申請時彈出編號最小的

但是對判斷當前哪些被訪問的內存重新進入空閑狀態(tài)是一個難題
最簡單的辦法是存起來每次掃一遍判斷
但這樣在極端數據時會TLE（題解里那個和數據構造者斗智斗勇的寫法就邪門）
那么怎么辦呢？

很容易想到也用一個優(yōu)先隊列維護
但問題是在訪問時內存到期時間會后延
而優(yōu)先隊列是不支持這一點的
但我們想到：
干脆不管原先在占用隊列里的那個內存了
直接再往里push一個新的
然后用num數組記錄每個內存在占用隊列里出現的次數
每次彈出時–；
然后當num=0時才是空閑的

寫但這里本題已經過了
但是我們又發(fā)現：占用隊列其實一定是先進先出的
那還優(yōu)先個球啊
直接隊列就行了
不過由于空閑隊列還是優(yōu)先隊列
所以時間復雜度還是nlogn
只是常數小了一點

多少快了點

AC！

代碼

#include<bits/stdc++.h> using namespace std; const int N=3e6+100; #define ll long long int n; int x,y,t; char s; struct node{int id,t;bool operator < (const node y)const{return t>y.t;} }; priority_queue<int,vector<int>,greater<int> >fre; queue<node>cpu; int num[N]; int main(){for(int i=1;i<=30000;i++) fre.push(i);while(scanf("%d %c",&t,&s)!=EOF){while(!cpu.empty()&&cpu.front().t<=t){int o=cpu.front().id;cpu.pop();if(--num[o]==0) fre.push(o); } // scanf(" %c ",&s); // printf("%c\n",&s);if(s=='+'){int now=fre.top();fre.pop();printf("%d\n",now);num[now]++;cpu.push((node){now,t+600});}else{scanf("%d",&x);if(x>30000) printf("-\n");else{if(num[x]){printf("+\n");num[x]++;cpu.push((node){x,t+600});}else{printf("-\n");}}}}return 0; } /* 1 + 1 + 1 + 2 . 2 2 . 3 3 . 30000 601 . 1 601 . 2 602 . 3 602 + 602 + 1202 . 2 */

總結

以上是生活随笔為你收集整理的内存管理（ybtoj-二叉堆）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。