保卫家园（小白版）

保卫家园（牛客） 题目链接

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中插入当前人的退伍时间，同时记录入过伍的人数的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：正如思路中的描述，要是当前人的入伍时间现役人的最早退伍时间，这种情况还是比较好理解的，当前人能够入伍了，因为有人可以在他入伍前退伍。 运生的子问题：为什么要让当前人与退伍比其入伍早中退伍最晚的人交换？让更早退伍的留在队伍里，为后面人尽可能多的入伍提供更大的可能。反正都要出去一个人，不如出去退伍尽可能晚的那个人，尽量保留退伍早的，这样后面人入伍的可能性就大了。

AC代码

//代码的讲解写在代码里的注释中了，建议复制到编译器看，因为有的注释比较长，需要左右拉动代码区，很不方便。

#include
using namespace std;
const int n=1e6+10;
struct person{
	int s,t;
}p[n];
bool cmp(person a,person b){
	return a.s>n>>k;
 	int cnt=k;
 	//cnt用于记录入过伍的人数。初始为k，因为下面直接先往multiset中插入了k个人的退伍时间
	for(int i=0;i>p[i].s>>p[i].t;
 
 	sort(p,p+n,cmp);
 	for(int i=0;i