[杭电多校3 | HDUOJ7170]Package Delivery（贪心 + 优先队列）

题目传送门：Problem - 7170 (hdu.edu.cn)

题意 / Problem

有N个包裹，可以在[l, r]的时间内去取，一次最多取k个，问最少取多少次可以取完所有包裹。

思路 / Thought

贪心的思想，确实很难想，但是题目做多了也容易想到，区间先排序。

将区间分两种方法排序，a数组根据r排序，b数组根据排序。

为使得取包裹次数尽可能少，就应该每次取包裹时间尽可能晚（因为这样可以使得每次取得的包裹尽可能达到k个），但是又一定要取到第一个包裹，所以每次取r最小的那个包裹（从前往后遍历a数组），并且在b数组中将l <= 最小的r的所有包裹都加入到队列里（注意只有b数组的元素入队），然后从队列中取出r最小的k个包裹，并标记为已经取走了，往下遍历a时遇到取走的就跳过。

这里可能会遇到一个问题：每次从队列中取走k个，有没有可能队列里还剩下一些包裹，后面会取不出来呢？不会的，因为a数组会遍历完，最坏的情况就是每次取一个，按照a中的顺序取。

利用双指针和优先队列可以完成以上操作。

代码 / Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int maxn = 1e5 + 9, MAXL = 55;
int N, K;

struct Node
{
	int l, r, id;
}a[maxn], b[maxn];
bitset<maxn> del;
bool cmpl(Node &u, Node &v){return u.l < v.l;}
bool cmpr(Node &u, Node &v){return u.r < v.r;}

struct cmp
{
	bool operator ()(const PII &a, const PII &b)const
	{
		return a.first > b.first;
	}
};

void solve()
{
	del.reset();
	cin >> N >> K;
	for(int i = 1;i <= N; ++ i)
	{
		cin >> a[i].l >> a[i].r;
		a[i].id = i;
		b[i] = a[i];
	}
	sort(a + 1,a + 1 + N, cmpr);
	sort(b + 1,b + 1 + N, cmpl);
	priority_queue<PII, vector<PII>, cmp> pq;
	
	int ans = 0;
	for(int i = 1, j = 1;i <= N; ++ i)//每次选择r最小的 
	{
		if(del[a[i].id])continue;//如果已经拿走了就跳过
		 
		while(j <= N && b[j].l <= a[i].r)//将可以拿走的都放到队列里 
		{
			pq.push({b[j].r, b[j].id});
			++ j;
		}
		ans ++;
		for(int t = 1;t <= K && !pq.empty(); ++ t)//每次选 r 最小的 k 个拿走 
		{
			del[pq.top().second] = true;
			pq.pop();
		}
	}
	cout << ans << '\n';
}

signed main()
{
	ios::sync_with_stdio(false);
	int _;cin >> _;
	while(_ --)solve();
	return 0;
}