自动搬运

查看原文

来自洛谷，原作者为

	huanxiong_2022 一只退役的的蒟蒻浣熊

搬运于2025-08-24 21:50:07，当前版本为作者最后更新于2023-09-22 15:47:41，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

P3553 [POI2013] INS-Inspector

摘要：

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

题意：

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

分析：

1. 发现 $k$ 似乎无法直接求得，考虑转化为检验前 $k$ 条是否合法。

2. 发现对于第 $i+1$ 条记录，直接检验其与前 $i$ 条是否冲突似乎不好实现，考虑每次检验 $O(m)$ 地遍历全部时间点，因此需要二分 $k$。

3. 如何检验

   1. 由于每个员工工作时间连续，所以将记录整合可以得到每个人必须要工作的区间，后文简称“必要区间”，整合区间可以得到每个时间点至少有多少人，检验记录是否小于最小值。以及是否存在对于同一时刻有不同记录。

   2. 通过了前一个检测的所有情况中，每个时间点的记录人数大于等于实际人数，因此若不限制人数一定合法（即每个人只工作于一个时间点）。问题转化为尝试使用不多于 $n$ 个人构造一个合法解。

   3. 沿时间轴检验并时刻判断即可，详见下文。个人认为本题难点是检测的思路和具体实现。

4. 检验的实现

   1. 思路：

      尝试用最优方式满足限制，并记录使用了多少人，看是否超过 $n$。

   2. 预处理：

      每个时间点 $i$ 的记录人数、有多少人的“必要区间”以当前时间开始或结束；即 $cnt_i,bg_i,ed_i$。

   3. 实现方案不唯一，部分名称含义如下：

      $now$：当前至少要有多少人（由且仅由 $st_i,ed_i$ 决定）。

      $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$，则需要从 $fre$ 中抽调一些。因为$now$ 是被 $bg_i,ed_i$ 锁定的，所以把抽调的加在 $exr$ 上，逻辑上为要求这些人提前工作。

      • 若 $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 初稿