P1844 阅览室 题解

思路

纯模拟题，每过一秒，会按顺序发生以下事情：

1. 看书的人剩下要看的时间减少1。

2. 如果有人看完这本书，还书。

3. 一些新的人进入阅览室。

4. 所有不在看书的人寻找图书。

5. 看不到自己想看的书的人进行登记。

注意到数据范围较小，于是考虑直接枚举时间，每秒模拟以上的事情。

为方便记录，开一个结构体，记录每个人要看的书，到的时间，是否看过每一本书，按等待时间作为第一关键字，到达时间作为第二关键字进行排序，只需要按顺序进行模拟即可。时间复杂度 $O(Tn\log n)$ 。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2000+5;
int T,n,sum;
int bk[N];//第i本书被看剩下的时间
struct node{
    int id[8],time[8],vis[8],res;//res 现在读书剩下的时间
    int t,k,wait;
    node(){wait=0;}
    bool operator<(const node &A)const{
        if(this->wait!=A.wait)return this->wait>A.wait; 
        return this->t<A.t;
    }
}a[N];
node tmp[N];
int main(){
    cin>>T>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].t>>a[i].k;
        for(int j=1;j<=a[i].k;j++){
            cin>>a[i].id[j]>>a[i].time[j];
        }
    }
    for(int i=0;i<T;i++){
        sort(a+1,a+1+n);
        for(int j=0;j<=2000;j++){
            if(bk[j])bk[j]--;
        }
        for(int j=1;j<=n;j++){
            node tp=a[j];
            if(tp.t>i){
                a[j]=tp;
                continue;
            }
            if(tp.res){
                tp.res--;
                a[j]=tp;
                continue;
            }
            int flag=0;
            for(int k=1;k<=tp.k;k++){
                if(!bk[tp.id[k]]&&!tp.vis[k]){
                    bk[tp.id[k]]=tp.time[k];
                    tp.wait=0;
                    sum++;
                    flag=1;
                    tp.vis[k]=1;
                    tp.res=tp.time[k]-1;
                    break;
                }
            }
            if(!flag){
                if(tp.wait<=0)tp.wait=1;
                else tp.wait++;
            }
            a[j]=tp;
        }
    }
    cout<<sum;
    return 0;
}