杭电多校 7170 Package Delivery

Problem Description
Little Q likes online shopping very much. In the next 109 days, there will be n packages delivered to the post office in total. Let’s label the next 109 days as day 1, day 2, …, day 109 respectively. For the i-th package, it will arrive at the post office at day li, and the deadline to take it back home is day ri, which means Little Q can take it back home at day x if and only if li≤x≤ri.

Every time Little Q comes to the post office, he can take at most k packages together back home at the same time. Note that Little Q can go to the post office multiple times during a single day. Please help Little Q determine how to take these n packages back home such that the number of times he will go to the post office is minimized.

Input
The first line contains a single integer T (1≤T≤3000), the number of test cases. For each test case:

The first line contains two integers n and k (1≤k≤n≤100000), denoting the number of packages and the number of packages Little Q can carry at the same time.

Each of the following n lines contains two integers li and ri (1≤li≤ri≤109), describing a package.

It is guaranteed that the sum of all n is at most 1000000.

Output
For each test case, output a single line containing an integer, denoting the minimum possible number of times that Little Q will go to the post office.

Sample Input

1
4 2
1 3
2 4
6 7
4 7
1
2
3
4
5
6

Sample Output

2
1

思路：
枚举每个包裹的$r_i$，取走包含$r_i$且并未去走的k个的区间。
做法：
读入部分：

	for(int i=0;i<n;i++)
		{
			arr[i].first=read();
			arr[i].second=read();
			ql[i]=i;
			qr[i]=i;
			del[i]=false;
		}
1
2
3
4
5
6
7
8

要用scanf或者read，用cin的话会超时
ql数组用于对包裹的$l$进行排序，qr数组用于对包裹的$r$进行排序
arr数组用于记录每个包裹的信息，del记录这个包裹是否被取走（已被取走为true，未取走为false）。
排序部分：

	sort(ql,ql+n,cmp1);
	sort(qr,qr+n,cmp2);
1
2

分别将包裹标号按照包裹的$l和r$进行排序
枚举$r$部分

	for(int i=0,j=0;i<n;i++)
		{
			if(del[qr[i]])
			{
				continue;
			}
			while(j<n && arr[ql[j]].first<=arr[qr[i]].second)
			{
				q.push({arr[ql[j]].second,ql[j]});
				j++;
			}
			res++;
			for(int u=0;u<k;u++)
			{
				if(q.empty())
				{
					break;
				}
				del[q.top().second]=1;
        		q.pop();
			}
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

如果该包裹已被取走，那么continue
接着枚举每一个可以取走的包裹，即这个包裹的$l$小于等于当前包裹的$r$，并将他们入队。
res++代表这次取包裹，故计数+1
优先队列按照可取的包裹的$r$进行排序，由于一次最多可取k个，故先去$r$最小的前k个。（因为$r$大的包裹可以以后再去，但是$r$小的包裹这次不取下次就没了！）
将已取的包裹标记一下，弹出。
如果q是空的，就意味着这次取不到k个包裹，就不取了。（比方说最多可以去3个包裹，但是这次去的时候快递站只有一个包裹，当u=0的时候取走了这个包裹，u=1的时候就没包裹了，q就空了 ）

完整代码：

#include
#include
#include
using namespace std;
const int N=100005;
typedef pair<int,int>PII;
PII arr[N];
int ql[N],qr[N];
bool del[N];
priority_queue<PII,vector<PII>,greater<PII>>q;
inline bool cmp1(int  x,int  y)
{
	PII a=arr[x];
	PII b=arr[y];
	if(a.first<b.first)
	{
		return true;
	}
	return false;
}
inline bool cmp2(int  x,int  y)
{
	PII a=arr[x];
	PII b=arr[y];
	if(a.second<b.second)
	{
		return true;
	}
	return false;
}
inline int read() {
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*f;
}
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int n,k;
		cin>>n>>k;
		for(int i=0;i<n;i++)
		{
			arr[i].first=read();
			arr[i].second=read();
			ql[i]=i;
			qr[i]=i;
			del[i]=false;
		}
		sort(ql,ql+n,cmp1);
		sort(qr,qr+n,cmp2);
		int res=0;
		for(int i=0,j=0;i<n;i++)
		{
			if(del[qr[i]])
			{
				continue;
			}
			while(j<n && arr[ql[j]].first<=arr[qr[i]].second)
			{
				q.push({arr[ql[j]].second,ql[j]});
				j++;
			}
			res++;
			for(int u=0;u<k;u++)
			{
				if(q.empty())
				{
					break;
				}
				del[q.top().second]=1;
        		q.pop();
			}
		}
		cout<<res<<endl;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81