P11257 题解

1. 题目分析

一道简单排序加字符串哈希的题，我很懒所以用的 unordered_map。
就是要注意一下题目中的老化期，也就是 k，只要到了老化期数据帧就会被立即删除。

2. 题目做法

首先就是在读入时用 unordered_map 将字符串转化为一个数字，方便计算。之后以时间点为关键字从小到大排序。
我们要用一个数组 v 记录当前存了多少个这种数据帧，以后依次遍历每个插入数据帧的时间点。先删除，再将当前加上。若一种数据帧在删除后或加上前数量为 0，则当前存有的数据帧种数减一或加一。最后记录个最大值就行了。

3. 代码

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
inline int read()
{
    int x=0;
    char c=getchar();
    while(c<'0'||c>'9')
        c=getchar();
    while(c>='0'&&c<='9')
        x=(x<<1)+(x<<3)+c-'0',c=getchar();
    return x;
}
int n,k,cnt;
unordered_map<string,int>ls;
struct node{
    int id,t;
}a[N];
inline bool cmp(node a1,node a2)
{
    return a1.t<a2.t;
}
int v[N],num,l,mx;
int main()
{
    n=read(),k=read();
    for(int i=1;i<=n;i++)
    {
        string s;
        cin>>s;
        ls[s]?1:ls[s]=++cnt;
        a[i]={ls[s],read()*60+read()};
    }
    sort(a+1,a+n+1,cmp);
    l=1,v[a[1].id]=num=mx=1;
    for(int i=2;i<=n;i++)
    {
        while(l<i&&a[l].t+k<=a[i].t)
            v[a[l].id]--,num-=!v[a[l].id],l++;
        num+=!v[a[i].id];
        v[a[i].id]++;
        mx=max(mx,num);
    }
    printf("%d",mx);
    return 0;
}