P1844 阅览室

Nostopathy · 2026-05-06 20:33:05 · 题解

有趣的模拟题。

此题用到的方法是使用排序来模拟题目中的优先顺序。

先梳理一下题目。

对于每个时刻，标记每个人该时刻想看的书。然后枚举其他读者，判断冲突并处理，分配这本书。

这里枚举的过程存在冗余计算。发现，题目中的规则是以开始等待的时间为第一关键字，到达时间为第二关键字进行优先分配。即可以用排序简化，直接按顺序依次分配。

具体地，维护当前读者开始等待的时间，每次分配时更新，每个新时刻重新排序。也需要记录每本书的状态以判断可行性。

#include <bits/stdc++.h>
using namespace std;
#define int long long

int T, n, b[1005], ans;

struct reader{
    int arr, k, s[6], t[6], wt;
    bool r[6];
    bool operator<(reader c) const{return (wt != c.wt ? wt < c.wt : arr < c.arr);}
} a[105];

signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    while(cin >> T >> n){
        for(int i = 1; i <= n; ++ i){
            cin >> a[i].arr >> a[i].k;
            ++ a[i].arr;
            for(int j = 1; j <= a[i].k; ++ j)
                cin >> a[i].s[j] >> a[i].t[j];
            a[i].wt = a[i].arr;
        }
        for(int t = 1; t <= T; ++ t){
            sort(a + 1, a + n + 1);
            for(int i = 1; i <= n; ++ i){
                if(a[i].arr > t || a[i].wt > t)
                    continue;
                for(int j = 1; j <= a[i].k; ++ j)
                    if(b[a[i].s[j]] <= t && !a[i].r[j]){
                        b[a[i].s[j]] = a[i].wt = t + a[i].t[j];
                        ++ ans;
                        a[i].r[j] = 1;
                        break;
                    }
            }
        }
        cout << ans << "\n";
    }

    return 0;
}