【模拟】AcWing 155. 内存分配
2022/2/17 7:13:12
本文主要是介绍【模拟】AcWing 155. 内存分配,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
有点毒瘤的模拟。
我用 \(\texttt{set}\) 乱搞编写了一个数据结构来维护,发现比很多人的代码跑得快,甚至在洛谷最优解前列,但是码量大了不少。
分析
实现的思路比较明显:
记一共有 \(m\) 个进程。
- 我们从 \(1\to m\) 枚举每个进程并进行处理。
- 在处理到第 \(i\) 个进程前,我们先进行结算(\(\texttt{account}\)),就是将在第 \(i\) 个进程所在的申请时刻之前能够结束的进程全部清除,并将等待队列中能够被加入的进程加入内存中。
- 然后对于当前进程:如果有足够的空间,那么就丢进去;反之,将其加入等待队列中。
可以发现,上面的模拟过程涉及对区间的赋值:当内存被占用的时候记为 \(1\),反之为 \(0\)。
对此,可以使用一个 \(\texttt{set}\) 来维护区间:
区间有三个属性:左右端点 \(l, r\),值 \(val(0/1)\)。
维护两种操作:
- \(\texttt{find(len):}\) 直接对 \(\texttt{set}\) 的元素(即区间)进行遍历,当区间值为 \(0\) 且长度 \(\geq len\) 时,返回该区间的左端点,如果没有则返回 \(-1\)。
- \(\texttt{eval(l, r, val):}\) 即区间赋值操作,当 \(val=0\) 时,也就是原来的区间从 \(1\to 0\),故检查该区间左、右区间是否也是 \(0\),如果是则需要进行合并再插入 \(\texttt{set}\);当 \(val=1\) 直接进行值的修改即可。
实现
// Problem: 内存分配 // Contest: AcWing // URL: https://www.acwing.com/problem/content/157/ // Memory Limit: 64 MB // Time Limit: 1000 ms // // Powered by CP Editor (https://cpeditor.org) #pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize("Ofast") #pragma GCC optimize("inline") #include<bits/stdc++.h> using namespace std; #define debug(x) cerr << #x << ": " << (x) << endl #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define dwn(i,a,b) for(int i=(a);i>=(b);i--) #define pb push_back #define all(x) (x).begin(), (x).end() #define x first #define y second using pii = pair<int, int>; using ll = long long; inline void read(int &x){ int s=0; x=1; char ch=getchar(); while(ch<'0' || ch>'9') {if(ch=='-')x=-1;ch=getchar();} while(ch>='0' && ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar(); x*=s; } const int N=10010; int n, m, ts, res; struct Event{ int t, m, p; }e[N]; struct Cmd{ int t, l, r; // end time, [l, r] bool operator < (const Cmd &o)const{ return t>o.t; } }; priority_queue<Cmd> clk; queue<pii> q; struct Seg{ int l, r; mutable bool val; bool operator < (const Seg &o)const{ return l<o.l; } int len(){ return r-l+1; } }; set<Seg> st; int find(int len){ for(auto i: st) if(!i.val && i.len()>=len) return i.l; return -1; } void eval(int l, int r, bool val){ auto it=--st.upper_bound({l, 0, 0}); if(val){ int L=it->l, R=it->r; st.erase(it); if(L<=l-1) st.insert({L, l-1, 0}); if(r+1<=R) st.insert({r+1, R, 0}); st.insert({l, r, 1}); } else{ auto L=it, R=it; if(it!=begin(st)) L--; if(it!=end(st)) R++; auto seg=*it; if(it!=L && L->val==0) seg.l=L->l, st.erase(L); if(R!=end(st) && R->val==0) seg.r=R->r, st.erase(R); seg.val=0; st.erase(it); st.insert(seg); } } void account(int lim){ while(clk.size() && clk.top().t<=lim){ auto tmp=clk.top(); clk.pop(); ts=tmp.t; int l=tmp.l, r=tmp.r; eval(l, r, 0); if(clk.size() && clk.top().t==tmp.t) continue; int k; while(q.size() && (k=find(q.front().x))!=-1){ auto [x, y]=q.front(); q.pop(); eval(k, k+x-1, 1); clk.push({ts+y, k, k+x-1}); } } } int main(){ cin>>n; int a, b, c; while(cin>>a>>b>>c, a || b || c) e[++m]={a, b, c}; st.insert({1, n, 0}); rep(i,1,m){ account(e[i].t); int k=find(e[i].m); ts=e[i].t; if(~k){ int l=k, r=k+e[i].m-1; eval(l, r, 1); clk.push({ts+e[i].p, l, r}); } else{ q.push({e[i].m, e[i].p}); res++; } } account(2e9+5); cout<<ts<<endl<<res<<endl; return 0; }
这篇关于【模拟】AcWing 155. 内存分配的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-05feign默认connecttimeout和readtimeout是多少-icode9专业技术文章分享
- 2024-07-05idea控制台,日志太多,导致部分想看得日志被刷走 搜不到-icode9专业技术文章分享
- 2024-07-05The server selected protocol version Tls10 is not accepted by client preferences [TLs12]-icode9专业技术文章分享
- 2024-07-05怎么清理项目缓存-icode9专业技术文章分享
- 2024-07-04安装 Eyoucms详细图文教程-icode9专业技术文章分享
- 2024-07-04ueditor 复制文章时,图片的链接是一个下载图片地址,该如何处理?-icode9专业技术文章分享
- 2024-07-04怎样判断host有没有对wordpress有缓存呢-icode9专业技术文章分享
- 2024-07-04具有编译功能的系统make后,无法ssh连接-icode9专业技术文章分享
- 2024-07-04make后如何升级ssh-icode9专业技术文章分享
- 2024-07-03微信支付提示下单账户与支付账户不一致-icode9专业技术文章分享