第三题

题目：参加博览会

有n场编号从0到n−1的博览会将要举办，编号为i的的博览会举办时间为[starti,endi]，即从第starti天到第endi天，包含第starti天和第endi天。

小明计划参加这些博览会，每天最多可以参加k场博览会。请问小明最多可以参加多少场博览会。需注意，小明不需要全程参加一场博览会，只需要在某一天参加即可。

输入描述

第一行输入包含两个整数n和k，n表示博览会的数量，k表示每天最多可以参加的博览会的数量，1≤n≤10^4，1≤k≤10。

以下n行每行包含两个整数start和end，表示第i场博览会的举办时间，1≤starti≤endi≤10^9。

输出描述

小明最多能参加的博览会数量。

样例输入一

3 1 1 2 2 3 1 1

样例输出一

3

说明

小明每天可以参加1场博览会，那么他可以在第1天参加第三场博览会，第2天参加第一场博览会，第3天参加第二场博览会，因此最多可以参加3场博览会。

样例输入二

5 2 1 1 2 2 1 2 2 2 1 1

样例输出二

4

说明

小明每天可以参加2场博览会，那么他可以在第1天参加第一场博览会和第五场博览会，第2天参加第二场博览会和第三场博览会，因此最多可以参加4场博览会。

题解：

1. 比较函数 `cmp`：按照博览会的开始时间升序排序，如果开始时间相同，则按照结束时间升序排序。

2. Work 函数

功能：计算小明最多可以参加多少场博览会。
变量解释：
day：当前处理的天数。
cnt：当前天小明参加的博览会数量。
ans：小明参加的博览会总数量。

逻辑：
如果 `day` 为0，表示当前没有处理的天数，更新为当前博览会的开始时间。
如果当前天数 `day` 在博览会的时间范围内，并且当天参加的博览会数量没有超过限制 `k`，则增加参加数量。
如果当天参加的博览会数量超过了限制 `k`，检查下一天是否在博览会的时间范围内，更新天数。
如果当前天数不在博览会的时间范围内，更新为当前博览会的开始时间。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 bool cmp(const pair<int,int>&a,const pair<int,int>&b){
 4     if(a.first<b.first)return 1;
 5     if(a.first>b.first)return 0;
 6     return a.second<b.second;
 7 }
 8 int Work(int&n,const vector<pair<int,int> >&a,int&k){
 9     int day=0,cnt=0,ans=0;
10     for(int i=1;i<=n;i++){
11         if(day==0){
12             day=a[i].first;
13             cnt++;
14             ans++;
15         }
16         else{
17             if(day>=a[i].first&&day<=a[i].second){
18                 if(cnt<k){
19                     cnt++;
20                     ans++;
21                 }
22                 else{
23                     if(day+1<=a[i].second){
24                         day++;
25                         cnt=1;
26                         ans++;
27                     }
28                     else{
29                         day=0;
30                         cnt=0;
31                     }
32                 }
33             }
34             else{
35                 day=a[i].first;
36                 cnt=1;
37                 ans++;
38             }
39         }
40     }
41     return ans;
42 }
43 int main(){
44     ios_base::sync_with_stdio(false);
45     cin.tie(NULL);
46     int n,k;
47     cin>>n>>k;
48     vector<pair<int,int> >a(n+1);
49     for(int i=1;i<=n;i++){
50         int s,e;
51         cin>>s>>e;
52         a[i]=make_pair(s,e);
53     }
54     sort(a.begin(),a.end(),cmp);
55     cout<<Work(n,a,k);
56     return 0;
57 }