P3553 [POI2013]INS-Inspector

2018-11-06 21:42:02


题意:有 $n$ 个人和 $m$ 条记录,每个人只会在一个连续的时间段工作,每条记录 $t,k,s$ 表示在 $t$ 时刻,编号为 $k$ 的人说除他以外还有 $s$ 个人,求一个最大的 $A$ ,使前 $A$ 条记录不产生矛盾


显然要二分答案,转化为判定性问题

定义几个变量:

$L_i,R_i$ 表示第 $i$ 个人一定在工作的时间段

$st_i,ed_i$ 表示 $i$ 时间点对应区间开始和结束的人数

$cnt_i$ 表示 $i$ 时间点剩余的人数


通过观察可以发现答案不可行的判断条件

  • 如果两条信息中,时间相同但剩余人数不同,那就不可行

  • 如果在一个人的工作区间中,有一条其他人的信息说除了他自己以外没人了,那也不可行


除去这两种情况,就一定可以构造出一种方案了

但是构造出的人数可能超过 $n$ 个

所以需要计算符合条件的最小人数

再定义几个变量:

$now$ 表示当前必需的人数

$tot$ 表示当前符合条件的最小总人数

$done$ 表示已经过了对应区间但还继续工作的人数

$todo$ 表示还没到对应区间但提前开始工作的人数

每到一个时刻 $i$ ,比较一下 $now+done+todo$ 和 $cnt_i$ 的大小关系

  • 如果 $now+done+todo<cnt_i$ ,那么说明当前人数不足,需要让一些人提前工作。所以增加 $tot$ ,并修改 $todo$

  • 如果 $now+done+todo>cnt_i$ ,那么说明人数多了,需要让一些人结束工作。那么就先让已经过了对应区间的人结束工作,如果还多,就再让提前工作的人结束工作。

这里产生了一个问题: $todo$ 表示的人对应区间还没到为什么可以结束工作呢?

因为不一定每一个人都有其对应的区间,这些人可以随时开始,随时停止,结束工作的 $todo$ 对应的是这一部分人

这真的是一道神题 $Orz$

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define reg register
using namespace std;
const int N=1e5+5;
struct node
{
    int x,tim,lef;
}q[N];
int n,m,L[N],R[N],st[N],ed[N],cnt[N],tot,now,done,todo;
inline int read()
{
    int x=0,w=1;
    char c=getchar();
    while (!isdigit(c)&&c!='-') c=getchar();
    if (c=='-') c=getchar(),w=-1;
    while (isdigit(c))
    {
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*w;
}
inline bool check(int k)
{
    tot=now=done=todo=0;
    for (reg int i=1;i<=n;i++) L[i]=N,R[i]=0;
    for (reg int i=1;i<=m;i++) st[i]=ed[i]=cnt[i]=0;
    for (reg int i=1;i<=k;i++)
    {
        L[q[i].x]=min(L[q[i].x],q[i].tim);
        R[q[i].x]=max(R[q[i].x],q[i].tim);
        if (cnt[q[i].tim]&&cnt[q[i].tim]!=q[i].lef) return 0;
        cnt[q[i].tim]=q[i].lef;
    }
    for (reg int i=1;i<=n;i++) if (R[i]) ++st[L[i]],++ed[R[i]];
    for (reg int i=1;i<=m;i++)
    {
        if (!cnt[i]) continue;
        now+=st[i]; if (now>cnt[i]) return 0;
        if (st[i]<=todo) todo-=st[i]; else tot+=st[i]-todo,todo=0;
        if (now+done+todo<cnt[i]) tot+=cnt[i]-now-done-todo,todo=cnt[i]-now-done;
        else if (now+todo>cnt[i]) todo=cnt[i]-now,done=0;
        else done=cnt[i]-now-todo;
        now-=ed[i]; done+=ed[i];
    }
    return tot<=n;
}
inline void work()
{
    n=read(),m=read();
    for (reg int i=1;i<=m;i++) q[i].tim=read(),q[i].x=read(),q[i].lef=read()+1;
    int l=2,r=m,ans=1;
    while (l<=r)
    {
        int mid=(l+r)>>1;
        if (check(mid)) ans=mid,l=mid+1;
        else r=mid-1;
    }
    printf("%d\n",ans);
}
int main()
{
    for (reg int T=read();T;T--) work();
    return 0;
}