自动搬运

查看原文

来自洛谷，原作者为

	gcwixsxr lxyddd

搬运于2025-08-24 22:14:09，当前版本为作者最后更新于2020-04-28 19:10:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

似乎这道题没有什么题解,

本蒟蒻来水题解啦

~~~~~~~ 大量文字警告 ~~~~~~~~~

这道题其实可以用链表加上模拟做出来

不妨先看看样例吧

题意可用下列表格表示(大致就这个意思)

大致思路:

模拟即可(模拟大法好!模拟大法好!模拟大法好!)

实现过程:

1.一个队列queue,一个动态数组vector,分别表示等待的队列,和内存条中的状态

vector<data> p;//内存条
queue<data> q;//等待队列

2.一个结构体data

struct data{
    int t,m,p,s;//时刻t,内存占用大小m,运行时间p,以及该数据占用的内存开始的位置s
    bool operator <(const data& x)const{
        return s<x.s;//重载运算符
    }
}x; //定义一个x

3.三个函数

(1)work函数:对新输入的数进行操作,在其中分别进行work_in和work_out两个子函数的操作,以及更新最早结束的进程w,同时判断能否推入内存,再推入等待数列的作用

void work(int t, int m, int p) {
    while (t >= w) work_out();//如果t已经大于最早可以结束的进程的时刻,那么进入work_out子函数
    x.t = t;
    x.m = m;
    x.p = p;//对x进行更新
    if (work_in(t)) w = min(w, t + p);//如果可以装入内存,则进入子函数work_in,并且更新最早可以结束的进程的时刻
    else q.push(x);//否则推入等待队列
}

(2)work_in子函数:判断能否进入内存,并且进行插入内存的操作 分别从第一个进程和内存条最开始之间、相邻两个进程之间、最后一个进程和内存条末之间判断内否插入内存

bool work_in(int t) {
    if (p.empty() || p[0].s >= x.m) {//如果p队列为空,或者队列首个进程的开始位置已经比x的占用空间大了,则有机可乘
        x.s = 0;//从内存条第0位开始占用
        x.t = t;//储存时刻t
        p.push_back(x);//推入内存条
        sort(p.begin(), p.end());//排序,将开始位置靠前的放在前面
        return 1;//返回值:可以插入
    }
    for (register int i = 1; i < p.size(); i++)
        if (p[i].s - (p[i-1].s + p[i-1].m) >= x.m) {//判断队列中是否两个进程间的内存大于x的内存(有机可乘)
            x.s = p[i-1].s + p[i-1].m;//从内存条第i-1个进程的下一位开始占用
            x.t = 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的内存(有机可乘)
        x.s = p[sz-1].s + p[sz-1].m;//从最后一个进程的下一位开始占用
        x.t = t;//储存时刻t
        p.push_back(x);//推入内存条
        sort(p.begin(), p.end());//排序,将开始位置靠前的放在前面
        return 1;//返回值:可以插入
    }
    return 0;//返回值:没有地方可以插入(进入等待队列)
}

(3)work_out子函数:将等待队列中的数弹出

void work_out() {
    int nw = INF;//将nw定为最大值
    for (register 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);//更新nw为最小值
    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;//更新w
}

下面是完整代码

抄代码者看这里

#include<bits/stdc++.h>
#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 (register 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 (register 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(register 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;
}

本蒟蒻写题解很用心,点个赞再走吧