毒瘤警告
这道题是道完完全全的模拟题
思路很清晰,代码很明了
可是A不了
这背后,究竟是道德的沦丧,还是人性的扭曲?
其实是读题的问题
这道题最大的难点就在于读懂题,然后捋明白内存分配的流程
流程如下:
对于每个时间点
1.首先将所有该结束的进程全部结束
2.然后考虑等待队列,按照队列顺序把队中元素逐一插入至无法插入
3.最后再考虑当前时间点申请内存的任务,可以插入就插入,不行就放入等待队列
然后我们可以考虑用链表来模拟当前内存情况,每次插入、删除复杂度均为$O(n)$,由于进行n次,总复杂度$O(n^2)$
yxc大佬用set来代替链表,代码短了很多,可插入的复杂度提升到$O(log_2n)$,总复杂度$O(n^2log_2n)$
但是考虑到n只有1000,这个复杂度可以接受
下附代码
链表版:(181ms)
#include<bits/stdc++.h>
using namespace std;
#define reg register
#define ll long long
#define ull unsigned long long
#define PII pair<ll,ll>
ll Size,cnt,idx = 2,t_now,ans;
ll t[1000010],m[1000010],p[1000010],nex[1000010],fa[1000010];
PII num[1000010];
priority_queue< PII,vector<PII>,greater<PII> > q_time;
queue<ll> q_wait;
ll insert(ll,ll);
void del(ll);
int main()
{
scanf("%lld",&Size);
num[2].first = Size + 1;
num[1].second = 0;
nex[1] = 2;
fa[2] = 1;
++cnt;
scanf("%lld%lld%lld",&t[cnt],&m[cnt],&p[cnt]);
q_time.push({t[cnt],INT_MAX});
while (q_time.size()){
t_now = q_time.top().first;
reg ll mode = q_time.top().second;
q_time.pop();
while (mode != INT_MAX){
del(mode);
if (q_time.top().first == t_now && q_time.top().second != INT_MAX && q_time.size()){
mode = q_time.top().second;
q_time.pop();
}
else
break;
}
while(q_wait.size()){
reg bool flag = 1;
for (reg int e = 1; e != 2; e = nex[e])
if (num[nex[e]].first - num[e].second - 1 >= m[q_wait.front()]){
q_time.push({t_now + p[q_wait.front()],insert(e,m[q_wait.front()])});
q_wait.pop();
flag = 0;
break;
}
if (flag)
break;
}
if (t_now == t[cnt]){
reg bool flag = 1;
for (reg int e = 1; e != 2; e = nex[e]){
if (num[nex[e]].first - num[e].second - 1 >= m[cnt]){
flag = 0;
q_time.push({t[cnt] + p[cnt],insert(e,m[cnt])});
break;
}
}
if (flag){
q_wait.push(cnt),++ans;
}
++cnt;
scanf("%lld%lld%lld",&t[cnt],&m[cnt],&p[cnt]);
if (!t[cnt] && !m[cnt] && !p[cnt])
continue;
q_time.push({t[cnt],INT_MAX});
}
}
printf("%lld\n%lld\n",t_now,ans);
return 0;
}
ll insert(ll e,ll Size)
{
num[++idx].first = num[e].second + 1;
num[idx].second = num[e].second + Size;
nex[idx] = nex[e];
fa[idx] = e;
nex[fa[idx]] = idx;
fa[nex[idx]] = idx;
return idx;
}
void del(ll e)
{
nex[fa[e]] = nex[e];
fa[nex[e]] = fa[e];
}
set版:(427ms)
yxc大佬写的
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <vector>
using namespace std;
typedef pair<int, int> PII;
int n;
queue<PII> waits; // (first: 内存长度,second: 占用时间)
set<PII> runs; // (first: 起始下标,sercond:长度)
priority_queue<PII, vector<PII>, greater<PII>> endts; // (first: 释放时间,second: 起始下标)
int tm, cnt;
bool give(int t, int m, int p)
{
for (auto it = runs.begin(); it != runs.end(); it ++ )
{
auto jt = it;
jt ++ ;
if (jt != runs.end())
{
if (m <= jt->first - (it->first + it->second - 1) - 1)
{
int start = it->first + it->second;
runs.insert({start, m});
endts.push({t + p, start});
return true;
}
}
}
return false;
}
void finish(int t)
{
while (endts.size() && endts.top().first <= t)
{
int f = endts.top().first;
while (endts.size() && endts.top().first == f)
{
auto top = endts.top();
endts.pop();
auto it = runs.lower_bound({top.second, 0});
runs.erase(it);
}
tm = f;
while (waits.size())
{
auto front = waits.front();
if (give(f, front.first, front.second))
{
waits.pop();
}
else break;
}
}
}
int main()
{
cin >> n;
int t, m, p;
runs.insert({-1, 1}), runs.insert({n, 1});
while (cin >> t >> m >> p, t || m || p)
{
finish(t);
if (!give(t, m, p))
{
waits.push({m, p});
cnt ++ ;
}
}
finish(2e9);
cout << tm << endl << cnt << endl;
return 0;
}
//作者:yxc
//链接:https://www.acwing.com/activity/content/code/content/36364/
//来源:AcWing
//著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
注意,set迭代器++复杂度是$O(log_2n)$, $\Theta(1)$ 的,而且用迭代器进行遍历复杂度必然是 $O(n)$ 的,故set版复杂度仍然是 $\Theta(n^2)$ ,特此更正
心态崩了,我当时写个链表干什么,简直是浪费时间
我应该手写平衡树的诶,我感觉改成
set
的话时间复杂度是没有变化的吧?跑得慢大概是 STL 常数大?set复杂度不应该带一个$log_2n$嘛?还是说我复杂度假了?
仔细想一下,如果手写平衡树应该是可以把每一次遍历优化到 $O(n)$ 的,但是如果使用set迭代器遍历的方式应该每一次是 $\Theta(n\log_2n)$ 的。一共有 $n$ 次操作,所以复杂度是 $\Theta(n^2\log_2n)$ 。
我还是太不熟悉Markdown和LaTeX了,写一个回复改了好多次我在网上查资料似乎迭代器++是 $O(1)$ 的???
你就当我没说吧,
反正常数变小不是坏事找学长求证之后,发现迭代器++不是 $O(1)$ 的,但是迭代器遍历确实也是 $O(n)$ 的,所以set版代码也是 $O(n^2)$ 的。。。学习了