P3553 [POI2013]INS-Inspector

题意：有$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; } ```