题解 P3553 [POI2023] INS-Inspector 督察

huanxiong_2022 · 2023-09-22 15:47:41 · 题解

P3553 [POI2013] INS-Inspector

摘要：

二分 k，每次沿时间轴检验前 mid 个是否冲突。
人的记录使他有一个必须存在的时间段。
逐时间点、尽可能使人数最少地满足记录要求，并检查是否使用超过 n 个人。

题意：

公司有 n 个员工和 m 个记录，每人只会在连续的一段时间内工作。现在给出 m 条记录分别是谁写的、什么时候写的以及写的时候除了他还有多少人。求最大的 k 使得前 k 条记录互不矛盾。

分析：

发现 k 似乎无法直接求得，考虑转化为检验前 k 条是否合法。
发现对于第 i+1 条记录，直接检验其与前 i 条是否冲突似乎不好实现，考虑每次检验 O(m) 地遍历全部时间点，因此需要二分 k。
如何检验
1. 由于每个员工工作时间连续，所以将记录整合可以得到每个人必须要工作的区间，后文简称“必要区间”，整合区间可以得到每个时间点至少有多少人，检验记录是否小于最小值。以及是否存在对于同一时刻有不同记录。
2. 通过了前一个检测的所有情况中，每个时间点的记录人数大于等于实际人数，因此若不限制人数一定合法（即每个人只工作于一个时间点）。问题转化为尝试使用不多于 n 个人构造一个合法解。
3. 沿时间轴检验并时刻判断即可，详见下文。个人认为本题难点是检测的思路和具体实现。
检验的实现
1. 思路：
  
  尝试用最优方式满足限制，并记录使用了多少人，看是否超过 n。
2. 预处理：
  
  每个时间点 i 的记录人数、有多少人的“必要区间”以当前时间开始或结束；即 cnt_i,bg_i,ed_i。
3. 实现方案不唯一，部分名称含义如下：
  $used$：已经使用过多少人。 $exl$：有多少人已经完成了必要区间，但是被迫延后下班。 $exr$：有多少人还没到必要区间，但是被迫提前上班。 $fre$：没有写记录的人，他们可以自由安排。 $left$：已经完成了工作，离开公司的人，后续安排与他们无关。注意，初始时认为上述全部为零；另外，上述名称在表述时逻辑上也视作集合。
4. 每一步的处理方法
  
  处理顺序：bg_i \rightarrow cnt_i \rightarrow ed_i。通过变量上的加减、逻辑上的人员调动（即从某一集合移动到另一集合），用 now,exl,exr 拼凑出 cnt_i
  - 当前点至少有 bg_i 个人开始工作，逻辑上,要把 exr 或者 fre 拿出 bg_i 个转化为 now，优先使用 exr，不足则增加 used。
  - 若 now+exl+exr 大于 cnt_i，则先弹掉 exl，仍多则弹掉 exr。
  - 在当前时间，有 ed_i 个人可以结束工作，让他们进入 exl 等待后续调度。
  - 最后，判断 used 是否超限。把上述步骤循环 m 次即可。

实现：

本人采用了 now,used,exl,exr 实现，用 used \ge n 判断不合法，仅在每次结尾判断即可，中间不需要判哪些变量是不是负数，个人认为比较好写。

注意，输入的是“除了他还有多少人”。

Code:

Link

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

const int maxn=1e5+10,inf=0x3f3f3f3f;
int T,n,m;
struct Log{int id,time,cnt;};
struct Staff{int bg,ed;};
struct Time{int cnt,bgcnt,edcnt,vis;};

Log g[maxn];
Staff p[maxn];
Time t[maxn];

bool check(int mid)
{
    for(int i=1;i<=n;i++)p[i]={0,0};
    for(int i=1;i<=m;i++)t[i]={0,0,0,0};
    for(int i=1;i<=n;i++)p[i]={inf,-inf};

    for(int i=1;i<=mid;i++)
    {
        //同一时刻的记录发生冲突
        if( t[g[i].time].cnt!=0 && t[g[i].time].cnt!=g[i].cnt)
        {
            return false;
        }
        t[g[i].time].cnt = g[i].cnt;
        t[g[i].time].vis=1;
        p[g[i].id].bg=min(p[g[i].id].bg,g[i].time);
        p[g[i].id].ed=max(p[g[i].id].ed,g[i].time);
    }
    for(int i=1;i<=n;i++)
    {
        if(p[i].bg!=inf)
            t[p[i].bg].bgcnt++,t[p[i].ed].edcnt++;
    }
    int now=0,used=0,exl=0,exr=0;
    //“必要区间”决定的人数
    //使用过的人数
    //可以下班但被迫加班的人数
    //暂时不用上班但是被迫提前的人数
    //即 exl 位于左侧的可拓展人数，exr右侧可拓展
    for(int i=1;i<=m;i++)
    {
        if(!t[i].vis)continue;

        now += t[i].bgcnt;

        if(now>t[i].cnt)
            return false;
        //“必要区间”与记录矛盾

        while (t[i].bgcnt--)
        {
            if(exr)exr--;
            else   used++;
        }
        //需要有一些人开始工作，有 exr 就让他开始，没有就新调人来
        //注意这里新增加的 used 是不可以被划分成 exl 的，他们会在结束自己的“必要区间”后加入 exl
        //可以写成 if else 的判断，但是 while 易于理解且不容易错

        if(now+exl+exr<t[i].cnt)
        {
            int d = t[i].cnt-now-exl-exr;
            exr+= d;  used+= d;
        }

        if(now+exl+exr>t[i].cnt)
        {
            int d = now+exl+exr-t[i].cnt;
            while(d--)
            {
                if(exl>0)exl--;
                else exr--;
            }
        }

        now-=t[i].edcnt; exl+=t[i].edcnt;

        if(used>n)
        {
            return false;
        }
    }
    return true;
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&g[i].time,&g[i].id,&g[i].cnt);
            g[i].cnt++;
        }
        int l=1,r=m;
        while(l<r)
        {
            // printf("l=%d,r=%d  ",l,r);
            int mid=(l+r+1)>>1;
            if(check(mid))l=mid;
            else r=mid-1;
        }
        printf("%d\n",l);
    }
    return 0;
}

upd: 2023.09.22 初稿