保卫家园（牛客）
题目链接
https://ac.nowcoder.com/acm/problem/205068
题目
题目描述：
为了抵御深渊的蔓延，被深渊毁掉家园的人们组建法兰不死队来镇压深渊。已知法兰不死队的最大编制为k，即队伍最多能有k人。有n个人想加入不死队，他们每人都有一个期望入伍时间s和退役时间t。入伍时间表示这个人如果要入伍的话只能在s时刻入伍。退役时间代表这个人可以在t时刻后退伍。因为战况严峻，所以队伍必须一直保持达到最大编制的状态。即队伍达到最大编制时候，队伍里有人可以退役的话，如果没有人来接替这个人的位置就不能退役。问最少有多少人没有进入法兰不死队的经历。
注：同一时刻，允许多个人一起入伍或者退伍，退伍时间要严格大于t 该人是否入伍是你来决定的 即就算没达到最多编制人数k，到了某人的入伍时间，你可以选择不让他入伍。
输入描述：
第一行两个数n、k，分别表示有n个人想入伍，最大编制为k人。
(1≤ n ≤10^ 6、1≤ k ≤n)
第二行开始每行两个数s、t 。（1≤ s ≤ t ≤10^ 6）
输出描述：
输出只有一行，表示最少有多少人没有入伍的经历。
样例：
示例1
输入
3 2
1 9
1 2
3 4
输出
0
示例2
输入
3 2
1 9
1 2
2 4
输出
1
说明:第二个人和第三个人之中一定有一个人无法入伍
示例3
输入
3 1
1 9
2 3
4 5
输出
1
说明:不让第一个人入伍的方案最优
思路
思路：
step1. 按入伍时间从小到大排序。
step2. 将前k个入伍的人的退伍时间插入到multiset中。
step3. 从第k+1个人开始遍历。
首先比较当前人的入伍时间与现役人的最小退伍时间的大小关系。
若当前人的入伍时间<=现役人的最早退伍时间，那么我们要找到现役人中的最晚退伍时间，比较现役人中最晚的退伍时间与当前人的退伍时间的大小，如果当前人的退伍时间<现役人中最晚的退伍时间，那么就让当前人去代替退伍最晚的现役人，本质上是在multiset里删除最晚退伍时间，同时插入当前人的退伍时间；如果当前人的退伍时间>=现役人中最晚的退伍时间，无需操作，保留原来队伍里的人即可。
若当前人的入伍时间>现役人的最早退伍时间，说明存在一个人要退伍，并且允许当前人入伍。要让退伍时间在当前人入伍时间之前且退伍时间最晚的人退伍，即删除multiset中比当前人退伍时间小且最大的时间。并且让当前人入伍，即往multiset中插入当前人的退伍时间，同时记录入过伍的人数的cnt自加。
step4. 输出n-cnt即可，表示总人数 - 入过伍的人数 = 未入过伍的人数。
分析思路
（这一部分用于分析“思路”中每一步的正确性和介绍如何理解，没有对应到具体的哪一步，所以看似比较混乱，但是我还是按照上述过程分析的）
Q1：为什么要按照入伍时间从小到大排序？
A1：（这里我想了好久才想明白）按照入伍时间去顺序遍历，本质上是时间上的顺序推进。相当于入伍的时间按1，2，3，……去循环，只不过我们通过排序，去遍历每个人的入伍时间实现的这一过程，同时这样的优点是省去了许多没必要的入伍时间。比如入伍时间有2，6，8，顺序循环时间的话就要按1，2，3，……去遍历，其实时间为1，3，4，5，7，9，……的时候并没有什么变化会发生，因此我们通过排序遍历入伍时间，实现了省略没必要的时间循环。遍历每个人的入伍时间，意味着到当前人入伍的时间了，可以对其进行操作，选择入伍还是不入伍，又或是在队伍里了。总而言之，本质上就是对时间的控制，让时间顺序进行，只不过这样就直接体现在了每个人的入伍时间上，更加的“简单”。
Q2：为什么插入multiset的是退伍时间？
A2：multiset中存储的是现役人的退伍时间。通过思路的描述不难发现，凡是涉及现役人时间上的比较，都是用现役人的退伍时间去比较的，而且用的都是有条件的最值去比较的，所以需要去查找现役人退伍时间中的最值，因此为了降低时间复杂度，将其插入到multiset中，通过自带的lower_bound & upper_bound去二分查找再合适不过了。
Q3：比较“当前人的入伍时间”与“现役人的最早退伍时间”大小关系的目的是什么？
A3：正如思路中的描述，要是当前人的入伍时间<=现役人的最早退伍时间，说明无法让一个人退伍，再让当前人入伍，因为当前人的入伍时间比现役人中任何一个人的退伍时间都要早。既然无法后来入伍，那就判断一下当前人的退伍时间是否比现役人中最晚的退伍时间早。要是当前人的退伍时间早，我们就可以让他去替换那个最晚退伍的人，实现缩短退伍的最晚时间，为后面人的尽可能多的入伍提供更大的可能。这里所说的替换，本质上是那个现役人中的退伍最晚的人没入伍过，只是假设他入伍了，现在让相对更合适的人，也就是当前人入伍，这也是为什么在这种情况的判断下，虽然队伍里的人发生交替，但是cnt没有自加的原因，因为实际上并没有人入伍或退伍，只是相当于完善队伍的状态。另一种大情况，当前人的入伍时间>现役人的最早退伍时间，这种情况还是比较好理解的，当前人能够入伍了，因为有人可以在他入伍前退伍。 运生的子问题：为什么要让当前人与退伍比其入伍早中退伍最晚的人交换？让更早退伍的留在队伍里，为后面人尽可能多的入伍提供更大的可能。反正都要出去一个人，不如出去退伍尽可能晚的那个人，尽量保留退伍早的，这样后面人入伍的可能性就大了。
AC代码
//代码的讲解写在代码里的注释中了，建议复制到编译器看，因为有的注释比较长，需要左右拉动代码区，很不方便。
#include<bits/stdc++.h>
using namespace std;
const int n=1e6+10;
struct person{
int s,t;
}p[n];
bool cmp(person a,person b){
return a.s<b.s;
}
multiset<int> a;
multiset<int>::iterator it;
int main(){
int n,k;
cin>>n>>k;
int cnt=k;
//cnt用于记录入过伍的人数。初始为k，因为下面直接先往multiset中插入了k个人的退伍时间
for(int i=0;i<n;i++)
cin>>p[i].s>>p[i].t;
sort(p,p+n,cmp);
for(int i=0;i<k;i++) a.insert(p[i].t);//直接先往multiset中插入了k个人的退伍时间
for(int i=k;i<n;i++){//遍历，除去已经插入的k个
if(p[i].s>(*a.begin())){//可以让一个人退伍，当前人入伍的情况//这里的begin()就是现役退伍的最早时间，因为放在multiset里了，所以是从小到大排好序的，第一个自然是最早的退役时间
it=a.lower_bound(p[i].s);//查找小于等于当前人入伍时间的最晚退伍时间
it--;//因为上面是小于等于，等于情况可不行，因此让it--，得到的刚好是小于当前人入伍时间的最晚退伍时间//举个例子（因为我当时这里理解了好一会）：1，2，2，3，3，3，4 it=lower_bound(3)，得到的it是第一个3的迭代器，而我们要的是严格小于的最晚退伍时间，所以it--，就是第二个2的迭代器
a.erase(it);//还是上面那个例子，a.erase(it)与a.erase(2)区别一下，前者是删除迭代器it位置的数字，而后者是删除所有的2，显然不同，这就是multiset中erase函数参数是迭代器与是数值的区别（因为我也是百度了一下才知道的，记下来）
a.insert(p[i].t);//插入值
cnt++;
}
else{
it=a.end();//与begin类似，end就是最大退伍时间对应的迭代器的下一个迭代器，因此下面进行it--
it--;
if(p[i].t<(*it)){//当前人的退伍时间早于现役人最晚退伍时间
a.erase(it);//同上描述
a.insert(p[i].t);
}
}
}
cout<<n-cnt;
}
最后声明一下，这个题我不会，是看大佬题解才会的，所以上面的都是扯淡（哈哈哈哈，你看完了我才告诉你，是不是很坑？哈哈哈，放心吧，上面的步骤都是对的，就是“分析思路”中，是我对这个题的理解，有不对的地方欢迎大家指正）
最后的最后，我还想问上天一句：我到底什么时候才能成为大佬啊啊啊！！！
