题目描述

输入格式

样例

样例输入1

4 10
0123456789ABCDEF 00:10
0000000000ABCDEF 08:11
0123456789ABCDEF 00:15
0000000000ABCDEF 00:11

样例输入2

3 60
0123456789ABCDEF 13:00
0000000000000000 14:00
0123456789ABCDEF 12:30

样例输出1

2

样例输出2

1

题目分析

真正意义上的签到题 (点名批评Day1T1) 虽然题面看起来很长，实际上题意就是最后一句话。给你一堆有编号且长度相同的区间，找出同时被最多不同区间包含的点，问这个点被多少个区间包含。
看到题目数据并不大，可以尝试用一维数组记录每个时间点有多少条数据帧，然后我们就会得到一个例如下图的东西（不同颜色代表不同的区间，最下一行fif_ifi​为区间个数）：

显而易见，拥有最多数据帧的是点5（因为先进行删除操作，所以蓝色区间对点6没有贡献）
很容易想到，每加入一个区间时，若之前出现过与其编号相同的区间，且它与这个区间重叠，那么可以看成与这个区间合并。否则，对于它包含的每个点，都可以提供1的贡献。注意：要先将每个时间转换为以分钟为单位计数；其次，因为输入顺序并不保证时间先后，因此我们要对这些区间要由插入时间从小到大进行排序。

首先我们能想到暴力，在每个区间加入时，若它并没有出现过，或没有与出现过的同编号区间重叠，则可以直接跑一遍循环将它包含的f[if[if[i]++；否则，就从它上次出现的过末尾下标+1开始遍历到这次的结尾。(此时的时间复杂度为O(nk)O(nk)O(nk)，已经可以过了）

核心代码

for(int i=1;i<=n;i++){for(int j=max(a[i].st,lst[a[i].s]+k);j<=a[i].st+k-1;j++)tim[j]++;lst[a[i].s]=a[i].st;}

优化

考虑对这个暴力进行优化，因为每次加入区间时都要跑一遍循环，很浪费时间，所以考虑将每次循环优化掉。这时候观察f数组，我们可以想到差分。每次插入一个区间，若没有出现过或没有与前面出现的同编号区间重叠，就在f数组里开始的下标+1，结束的下标-1；否则就在上次出现的结尾+1，这次的结尾-1（合并区间）。复杂度为O(nlogn)O(nlogn)O(nlogn)

代码

#include
using namespace std;
map lst;
int tim[5005],n,k;
struct node{string s;int st;
}a[100005]; 
int chan(string s)//将时间转换为以分钟为单位
{int ans=0,k=0;s+=':';for(int i=0;iif(s[i]!=':') k=k*10+(s[i]-'0');else ans=ans*60+k,k=0;}return ans;
}
bool cmp(node x,node y)
{return x.stfreopen("switch.in","r",stdin);freopen("switch.out","w",stdout);cin>>n>>k;for(int i=1;i<=n;i++){cin>>a[i].s;string t;cin>>t;a[i].st=chan(t);}	sort(a+1,a+n+1,cmp);for(int i=1;i<=n;i++){int en=a[i].st+k;if(lst[a[i].s]!=0&&lst[a[i].s]+k>=a[i].st)//出现过且重叠{tim[lst[a[i].s]+k]++;tim[a[i].st+k]--;}else{tim[a[i].st]++;tim[a[i].st+k]--;}lst[a[i].s]=a[i].st;}int maxn=0,sum=0;for(int i=0;i<=5000;i++){sum+=tim[i];maxn=max(maxn,sum);}cout<