题解：P3553 [POI 2013] INS-Inspector
STDLRZ
·
·
题解
这道题很妙。
\tt 100~pts 做法
首先，一眼二分（问题的解有单调性，前半部分可以，后半部分不可以），将原问题转为判定性问题。
问题被转换为：判断前 k 条信息是否有矛盾。
但是，这个问题还是没有办法做啊。
- 妙点：我们可以先不管那些不确定因素，先考虑确定因素。
对的，直接考虑是没有办法的，我也无能为力。
但是，如果我们可以将确定因素和不确定因素分开，说不定这个问题就解决了呢？
如果一个人在多个时间点打了卡，因为题目说每一个人的工作时间是连续的，所以我们可以记录他最开始是什么时候打卡的，和他最后是什么时候打卡的，我们就知道他至少要工作的是哪一段时间。
这样，我们就可以将每一个时间点必须工作的人数给记录下来。
如果有记录的信息说，时间点 t 的工作人数为 x，但是必须工作的人数比他多的话，这就一定矛盾了，直接 return 0 即可。
先不要着急，我们来讨论一下。
首先，我们得知当前必须工作的人一定比 $x$（上面的定义）要多（至少等于）。
也就是说，我们还要再加一些人。
我们可以拉一些自由人（那些不目前需要工作的人），来让他们工作。
那我们要先拉哪些人呢？
我们可以先拉那些已经下班的人，强制他们继续工作，这样我们就可以尽量减少人力成本了，不需要新的人过来工作。
但是如果那些已经下班的人彻底下班了呢？
- 我们定义彻底下班的人为，加班的工作也做完了，且在之前的某个时刻**不需要他工作了，让他下班了**的那些人数。
像这些人肯定是不能拉回来的，因为我们知道，每一个人的工作区间是连续的，之前已经有一个时间点他没有工作了，如果把他拉回来工作，证明之前的那个**不需要他的时间点**他又要工作了，那就不满足条件了。
所以，这些人我们不能拉回来叫他们工作，只能让他们回去。
如果把那些没有彻底下班的人全部拉过来还不够，我们就只能让一些人**提前上班了**。
但是，请注意：我们在人数太多的时候可不可以让一些人从提前上班变成不提前上班呢？
此时，我们发现，如果这些人走了，那他们就**只能是自由人**，这些自由人**原本是不需要工作的**（没有必须工作的时间段），只能让他们走，其他的不能走。
为了代码的实现方便，我们将这些自由人和提前上班的人给合并了一下，这个逻辑也是没问题的。当然，如果你非要和提前下班的人合并，也是可以的，但不过有点难写。
所以，我们合并之后，就相当于让提前上班的人走了，且没有办法让他们回来了（因为是自由人嘛，且现在不需要他了，则以后也不能用他了）。
考虑让一些人上班的时候该怎么办。
我们可以在那些提前上班的人里面抽几个出来让他们工作（实际上编号是没有用的，因为我们的编号可以调换，而且我们也不需要知道是谁什么时候上班，只需要知道有几个人要现在上班就可以了）。
但是如果没有提前上班的人呢？我们要叫他起来工作了，~~不能睡懒觉了。~~
为什么前面让自由人和提前上班的人合并没有影响呢？因为我们的编号可以**调换！**
比如说，我们原本是编号为 $3$ 的人是自由人，$1$ 是现在要工作的人，现在 $1,3$ 都提前工作了，我们要抽调一个人出来工作。
假设我们运气非常不好，抽到了编号为 $3$ 的人，但是可能他本来就不需要工作，于是我们让这个人变成编号为 $1$ 的人，剩下一个编号为 $3$ 的人就和那个原本是编号为 $1$ 的人调换，这样就没有问题了。
如果还没有理解可以看看代码中的附说明。
我们总结一下过程：
- 首先，我们定义 `used` 表示已经使用过的人数，`tiq` 表示正在提前上班的人有几个，`yah` 表示还没有彻底下班（还在工作），但是原本已经不需要工作的人有几个，`now` 表示现在必须要工作的人有几个。
- 如果当前的信息中有 $x$ 个人在工作，且 $x$ 比当前必须工作的人要小，证明肯定矛盾（和确定性的东西矛盾了，那不是矛盾是什么？），返回 `0`。
- 否则，我们从提前工作的人里面抽调一些人出来工作，也就是 `--tiq,++now`（因为这些人这个时间必须要工作了嘛，且他们现在也不是提前工作的人了）。
- 如果还不够，那就新增一些人（叫一些人起来干活），直接 `++now` 即可。
- 如果当前干活的总人数（`now+tiq+yah`）比当前信息要少，我们就只能新增一些自由人，让 `tiq+=need,used+=need`（`need` 表示需要的人数，我们已经将 `tiq` 和自由人这两个变量合并了，且正确性在前面已经叙述）。
- 否则，证明人数多了，我们就先让一些原本就要下班的人下班（表示他们彻底下班了），然后 `--yah`；如果已经没有延后下班的人，那就减少一些自由人，让这些自由人自由去，也就是 `--tiq`，直到和当前信息吻合即可。
- 接着，让那些准备在当前节点下班的人进入加班工作组，继续努力工作~~压榨员工~~。至于要不要他们继续工作就看下个时间点了，这个我们前面已经涉及到这部分了，不能重复处理。
- 判断 `used` 是否超过 $n$，如果超过 $n$，证明我们只有 $n$ 的人力但是不够用了，返回 `0`，否则继续新的下一轮即可。
代码：
```cpp
#include<bits/stdc++.h>
#define x0 x_0
#define x1 x_1
#define y0 y_0
#define y1 y_1
#define yn y_n
#define j0 j_0
#define j1 j_1
#define k0 k_0
#define k1 k_1
#define d0 d_0
#define d1 d_1
#define LL long long
#define LD long double
#define ZPB push_back
#define ZPF push_front
using namespace std;
int z,n,m;
struct node{
int t,id,wrki;
// t: 当前时间
// id: 记录者
// wrki: 当前时间 t 有 wrki 个人正在工作
};
node info[100010];
// info，展开是 information，表示记录的信息。
int st[100010],ed[100010],tbg[100010],tfn[100010],twki[100010];
// st[i]: 第 i 个人必须工作时间段的开始时间。
// ed[i]: 第 i 个人必须工作时间段的截止时间。
// tbg[i]: 在第 i 个时间点中，有几个人预计要开始工作。
// tfn[i]: 在第 i 个时间点中，有几个人预计要停止工作。
// twki[i]: 在第 i 个时间点中，有几个人正在工作。
bool check(int mid){
for(int i=1;i<=n;++i) st[i]=1145141919,ed[i]=-1145141919; // 其实只要 st[i]>ed[i] 即可
for(int i=1;i<=m;++i) tbg[i]=tfn[i]=twki[i]=0; // 初始化
for(int i=1;i<=mid;++i){
#define t info[i].t
#define wrki info[i].wrki
#define id info[i].id
if(twki[t] && (twki[t]^wrki)) return 0; // 如果同一个时间的信息有矛盾（工作人数记录的不一样），return 0
twki[t]=wrki,st[id]=min(st[id],t),ed[id]=max(ed[id],t); // 更新每一个人的必须工作时间段和当前时间 t 有几个人在工作。
#undef t
#undef wrki
#undef id
}
for(int i=1;i<=n;++i)
if(st[i]^1145141919) ++tbg[st[i]],++tfn[ed[i]]; // 更新 tbg 和 tfn
int now=0,tiq=0,yah=0,used=0,x; // 如总结中的定义所述，x 什么都不是，不用管
for(int i=1;i<=m;++i){
if(!twki[i]) continue;
now+=tbg[i],x=tbg[i]; // 有 tbg[i] 正式加入工作
if(now>twki[i]) return 0; // 如上面的文字所述
while(x--){
if(tiq) --tiq; // 优先让那些提前工作的人正式开始工作
else ++used; // 如果人数不够那就加人
}
if(now+tiq+yah<twki[i]){ // 1: 人数不够
int need=twki[i]-now-tiq-yah;
tiq+=need,used+=need; // 新加入一些自由人
}else{ // 2: 人数不够
x=now+tiq+yah-twki[i];
while(x--){
if(yah) --yah; // 如果有延迟下班的人，让他们跑路，彻底下班，且以后不再使用到他们
else --tiq; // 否则，让一些自由人走，如果我们减去的是那些有必要工作时间段的人，调换一下编号即可
}
}
yah+=tfn[i],now-=tfn[i]; // 让那些在时间点 i 下班的人延迟下班
if(used>n) return 0; // 已经超过使用人数， return 0
}
return 1; // 前 mid 条信息没有问题，return 1
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>z;
while(z--){
cin>>n>>m;
for(int i=1;i<=m;++i) cin>>info[i].t>>info[i].id>>info[i].wrki,++info[i].wrki;
int L=1,R=m,ans=0;
while(L<=R){ // 二分，不用多说，至于为什么 L 可以不是 0，因为第一条信息一定不会出现矛盾（自己应该不会和自己矛盾吧）
int mid=(L+R)>>1;
if(check(mid)) L=mid+1,ans=mid;
else R=mid-1;
}
cout<<ans<<"\n";
}
return 0;
}
/*
附说明：为什么每一次都有可以调换编号的人呢？不是每一个人都是自由人啊，万一当前没有自由人可以调换怎么办？
我们可以先看作 tiq 里面的所有人目前都是自由人，这样就不用考虑调换编号了。
但是我们在选一些人出来正式开始工作的那个时候又怎么办？
我们就可以让这些自由人和原本要工作的人的编号交换，让他们变成现在要工作的人但是提前上班了的那部分人，
然后把他们给 pop 出去。
因为我们每一次把自由人转为那些有必要工作区间的人时就立马让他加入工作了，所以这是没有问题的。
逻辑上可以理解为这些人原本就是提前上班了的人（不是自由人），但不过我们只是那个时候才更新他的身份而已，
之前没有更新他的身份是因为还不能确定他到底是自由人还是非自由人。
*/
```