题意
时
刻
T
内存占用情况
进程事件
0
1
2
3
4
5
6
7
8
9
进程A申请空间（M=3, P=10）<成功>
1
A
2
A
B
进程B申请空间（M=4, P=3）<成功>
3
A
B
进程C申请空间（M=4, P=4）<失败进入等待队列>
4
A
B
D
进程D申请空间（M=1, P=4）<成功>
5
A
C
D
进程B结束，释放空间
进程C从等待队列取出，分配空间
进程E申请空间（M=3, P=4）<失败进入等待队列>
6
A
C
D
7
A
C
D
8
A
C
E
进程D结束，释放空间
进程E从等待队列取出，分配空间
9
A
E
进程C结束，释放空间
10
A
E
11
E
进程A结束，释放空间
12
进程E结束，释放空间
具体题目看http://poj.org/problem?id=1193 是中文的
思路
自己一开始想暴力模拟，单身很难实现
后来“抄”了std的代码，用的是链表+二叉堆（有吗？）
代码
//author: sysky
//copy: XuHt
#include<cstdio>
#include<vector>
#include<algorithm>
#include<queue>
#define INF 0x3fffffff
using namespace std;
int n,w=INF,cnt=
0;
struct data{
int t,m,p,s;
bool operator <(
const data x)
const{
return s<
x.s;
}
}x;
vector<data>
p;
queue<data>
q;
bool work_in(
int t) {
if (p.empty() || p[
0].s >=
x.m) {
x.s =
0;
x.t =
t;
p.push_back(x);
sort(p.begin(), p.end());
return 1;
}
for (unsigned
int i =
1; i < p.size(); i++
)
if (p[i].s - (p[i-
1].s + p[i-
1].m) >=
x.m) {
x.s = p[i-
1].s + p[i-
1].m;
x.t =
t;
p.push_back(x);
sort(p.begin(), p.end());
return 1;
}
int sz =
p.size();
if (n - (p[sz-
1].s + p[sz-
1].m) >=
x.m) {
x.s = p[sz-
1].s + p[sz-
1].m;
x.t =
t;
p.push_back(x);
sort(p.begin(), p.end());
return 1;
}
return 0;
}
void work_out() {
int nw =
INF;
for (unsigned
int i =
0; i < p.size(); i++
)
if (p[i].t + p[i].p == w) p.erase(p.begin() + i--
);
else nw = min(nw, p[i].t +
p[i].p);
while (q.size()) {
x =
q.front();
if (work_in(w)) {
nw = min(nw, q.front().t +
q.front().p);
q.pop();
cnt++
;
} else break;
}
w =
nw;
}
void work(
int t,
int m,
int p) {
while (t >=
w) work_out();
x.t =
t;
x.m =
m;
x.p =
p;
if (work_in(t)) w = min(w, t +
p);
else q.push(x);
}
int main()
{
scanf("%d",&
n);
int t0,m0,p0;
while(scanf(
"%d%d%d",&t0,&m0,&p0)==
3 &&!(t0==
0&&m0==
0&&p0==
0))
work(t0,m0,p0);
while(q.size()) work_out();
int ans=
w;
for(
int i=
0;i<p.size();i++
)
ans=max(ans,p[i].t+
p[i].p);
printf("%d\n%d\n",ans,cnt);
return 0;
}
我太菜了
转载于:https://www.cnblogs.com/lincold/p/10228889.html
相关资源：JAVA上百实例源码以及开源项目
