（2022杭电多校三）1009.Package Delivery（贪心）

题目：

 样例输入：

1
4 2
1 3
2 4
6 7
4 7

样例输出：

2

题意：多组测试，对于每一组测试，先给出一个n和k，n代表快递个数，k代表我们一次最多能拿的快递数，接下来n行每行给出两个数，分别代表快递的到达时间以及截至时间，我们必须要在截止时间之前把快递取走，一天可以取多次快递，问我们取完所有的快递至少需要取的次数。

分析：这显然是一道贪心题，既然一天可以取快递的次数不受限制，那么我们就可以尽量把取快递的时间往后延，这样我们的快递数会越来越多，相应地一次取出来的快递数也可能会更多，我们只在截至时间取快递，我们一次尽可能地多取快递，首先我们需要先对所有的快递按照l升序排列，然后从前往后遍历，我们可以设置一个时间t代表我们当前的时间点，我们用一个队列记录当前时间已经到达且还未取出的快递，则所有l<t的快递都应该被加入到队列中（还未取出的快递），这个队列按照r升序排列，因为当t等于一个快递的截至时间时我们必须要花费一次把他取出。

当t到达一个快递的截至时间时队列中的快递数目有两种情况：

（1）小于等于k个，那我们直接全部取出即可

（2）大于k个，那么我们就把r从小到达取出k个即可（即使没有取完也只取k个）

之所以当快递数大于k个时我们不把它全部取完是因为我们先把特别紧急的快递取了，那么剩余的快递如果还没有到达截至时间，我们可以稍微等等，之后或许可以与其他后到的快递一起取出，这样答案或许会更优

这就是这道题目的贪心策略了，细节见代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int N=400010;
typedef pair<int,int> PII;
int l[N],r[N];
struct node{
	int l,r;
}p[N];
bool cmp(node a,node b)
{
	return a.l<b.l;
}
void solve()
{
	int n,k;
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&p[i].l,&p[i].r);
	sort(p+1,p+n+1,cmp);
	priority_queue<PII,vector<PII>,greater<PII> >q;
	while(!q.empty()) q.pop();
	q.push({p[1].r,p[1].l});//先放r可以避免手写排序函数 
	int t=p[1].r,ans=0;
	for(int i=2;i<=n;)
	{
		while(i<=n&&(p[i].l<=t||t==-1))
		{
			if(t==-1) t=p[i].r;
			t=min(t,p[i].r);
			q.push({p[i].r,p[i].l});
			i++;
		}
		if(!q.empty())
		{
			ans++;
			if(q.size()<=k)
			{
				while(!q.empty())	q.pop();
				t=-1;
			}
			else
			{
				int tt=k;
				while(tt--)	  q.pop();
				t=q.top().first;
			}
		}
	}
	ans+=(q.size()+k-1)/k;//最后不要忘记把所有快递全部取出来 
	printf("%d\n",ans);	
}
int main()
{
	int _;
	cin>>_;
	while(_--) solve();
	return 0;
}