题解：P6928 [ICPC 2016 WF] What Really Happened on Mars?

· · 题解

题目传送门。

一。题目意思

首先需要做一个简化系统，有 t 个进程和 r 种不同的资源，所有进程都需要资源，并且执行指令，最终输出每个进程的全部执行完成时间。 每个进程的优先级，题目中保证不同，一一不等，优先级会随同所占有的资源进行实时动态变化，整个模拟过程需要严格按照调度规则推进。

二。指令含义拆解

1.compute

相当于运行，进行计算，但是这条指令才算执行完毕，进程才能继续执行下一条指令。

2.lock k

当前进程想要申请占用编号为 k 的资源。进程会执行这条指令后，然后会将资源 k 的持有者标记为自己。题目在初始状态下，所有的资源全部都是空闲的，没有被任何一个进程所占用。

3.unlock k

从字面就能看出，是上一个指令的反义词，如果说上一道题是一把锁，那么这道题就是一把钥匙，简单来说就是将资源 k 释放回空闲状态。

三。核心逻辑

整个系统不是简单的先来先服务，而是基于‌动态优先级的抢占式，思想如下。

1. 优先级动态更新

进程的实际调度优先级其实不是固定不变的，大概率会随着它持有的资源与其他相关进程的状态不断更新。

2. 阻塞的机制

如果一个进程想要使用 x 资源，但是这个资源已经被占用并且使用，那么就形成了阻塞，那么此进程就暂时无法运行。

3. 推进

进程从 0 开始循环，并且模拟，任何一个周期都会先激活所有到达起始时间的进程，然后再更新所有进程的阻塞状态，最后呢，选出当前优先级最高的非阻塞进程执行一条指令。 如果没有需要执行的任何进程，那么就会向前推进，并且进行等待。

四。代码

#include<cstdio>
int clk,n,m,f[21],q[21];
struct node;
node*top;
void build();
node*find_top();
int id(node*);
node&at(int);
void max_eq(int&s,int t){
    if(s<t)
        s=t;
}
struct node{
    char s[100][8];
    int a,b,c,d,k,t,v[100];
    bool r,l;
    void scan(){//读取单个任务的数据
        scanf("%d%d%d",&t,&b,&a);
        for(int i=0;i!=a;++i){
            scanf("%s",s[i]);
            sscanf(s[i]+1,"%d",v+i);
            if(*s[i]==76)
                max_eq(q[v[i]],b);
        }
    }
    bool test(int i){
        return*s[k]==76&&(v[k]==i||c<=q[i]);
    }
    void run(){
        c=b;
        for(int i=1;i<=n;++i)
            if(at(i).r&&!at(i).d)
                for(int j=1;j<=m;++j)
                    if(f[j]==i&&test(j)){
                        l=1;
                        max_eq(at(i).c,c);
                    }
        r=1;
    }
    void next(){
        if(*s[k]==76)
            f[v[k]]=id(this);
        if(*s[k]==85){
            f[v[k]]=0;
            c=b;
            for(int j=1;j<=m;++j)
                if(f[j]==id(this))
                    for(int i=1;i<=n;++i)
                        if(i!=id(this)&&at(i).r&&!at(i).d&&at(i).test(j))
                            max_eq(c,at(i).c);
        }
        if((k+=*s[k]!=67||++clk&&!--v[k])==a)
            d=clk;
    }
}task[21];
int id(node*p){
    return p-task;//指针计算偏移量
}
node&at(int i){
    return task[i];
}
void build(){
    for(int i=1;i<=n;++i)
        if(at(i).r&&!at(i).d){
            at(i).l=0;
            for(int j=1;j<=m;++j)
                at(i).l|=f[j]&&f[j]!=i&&at(i).test(j);
        }
}
node*find_top(){
    top=0;
    for(int i=1;i<=n;++i)
        if(at(i).r&&!at(i).d&&!at(i).l&&(!top||at(i).c>top->c))
            top=&at(i);
    return top;
}
bool ended(){
    for(int i=1;i<=n;++i)
        if(!at(i).d)
            return 0;
    return 1;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
        at(i).scan();
    while(!ended()){
        for(int i=1;i<=n;++i)
            if(!at(i).r&&at(i).t==clk)
                at(i).run();
        build();//更新阻塞状态,有风险
        if(find_top()||!++clk)
            top->next();
    }
    for(int i=1;i<=n;++i)
        printf("%d\n",at(i).d);
}

在代码高亮段，其实不是很完美，但是勉强能过，所以此处就不展示优化代码了。

::::info[使用AI说明]{open} 本文经文心一言润色。 ::::