题解：P11257 [GDKOI2023 普及组] 交换机

DeepSleep_Zzz · 2024-12-05 00:16:19 · 题解

begin

P11257 题目传送门

前置算法

基础：模拟。

优化算法：前缀和，差分。
（如果不了解的话就先不用看优化算法了，把基础版搞懂这题就够用。当然如果能了解一下肯定是最好的。）

题目简述

这个出题人真的太良心了，居然在题目最后一行提示我们：

简单来说，需要维护一个字符串集合 S，有若干次插入操作，每次插入操作包含一个字符串以及一个有效时间区间（区间长度为定值），需要求出所有时间内，字符串集合 S 大小的最大值。

呜呜呜，这么好的出题人上哪找啊，连题目简化的时间都省了。

ok 废话不多说，接下来切入正题。

思路

这是一道比较思路容易、细节比较多的模拟题。根据题意简述模拟即可。

就像线段覆盖一样，我们要找到覆盖次数最多的一条线段，并输出其覆盖次数。

我们可以定义一个结构体来存储源 \texttt {MAC} 地址以及传入时间（用 t 来表示）。然后按照传入时间升序排列。从前往后依次模拟。

再建立一个数组 mac，mac_i 表示第 i 分钟有多少个有效数据存储在交换机内。

底层思路：在接收到某一条 \texttt {MAC} 地址后，将 [mac_t,mac_{t+k}) 都增加 1。

需要特别注意的是：

有可能在上一条 \texttt {MAC} 数据的老化期未到之时，又有一条一模一样的 \texttt {MAC} 数据传入，此时我们需要避免重复计算。
有可能在上一条 \texttt {MAC} 数据已经删除过后，又有一条一模一样的 \texttt {MAC} 数据传入，此时我们正常模拟即可。
特判老化期超出 1440 分钟的情况，否则你将会喜提一片 RE。

看到这里你就会发现，这正是 map 家族的强项。

最后输出 mac 数组的最大值即可。

时间复杂度

时间复杂度 O(nt)（此处 t 为一天中的总分钟数）。最坏情况下程序会运行 10^5 \times 1440=1.44 \times 10^8 次，再加上一些常数，略微极限，但是开了 O2 优化之后时间还是够用的（或者可能是~~数据过水~~）。

具体处理详见代码。

Code 1.0

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
struct exchange
{
    string s; // MAC 原地址
    ll t; // 传入时间
    bool operator<(const exchange &ech)const
    {
        return t<ech.t;
    } // 重载小于符号（等价于 cmp 函数，这样就不用写 sort 后面的 cmp 函数了。）
}a[100010];
ll n,k,h,m;
ll mac[1450]; // 记录每分钟的数据数量
char c; // 到后面你就知道这是干嘛的了
unordered_map<string,ll> um; // 无序映射，与 map 相时间复杂度比少了个 log，运行时间更快。
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); // 读入优化
    cin>>n>>k;
    for (ll i=1;i<=n;i++)
    {
        cin>>a[i].s;
        cin>>h>>c>>m; // 等价于 scanf("%lld:%lld",&h,&m)，因为我解绑了 cout 所以这里用 char c 来过滤掉中间的冒号。
        a[i].t=h*60+m+1; // +1 比较方便处理
    }
    sort(a+1,a+n+1);
    for (ll i=1;i<=n;i++)
    {
        for (ll j=max(a[i].t,um[a[i].s]+k);j<min(1441LL,a[i].t+k);j++) // 一些特殊处理，对应着上面提到的 3 条注意事项。
        {
            mac[j]++;
        } // 统计存在时间
        um[a[i].s]=a[i].t; // 更新时间
    }
    cout<<*max_element(mac+1,mac+1441); // 求 mac 数组的最大值
    return 0;
}

小小优化

前面也说过了，O(nt) 的时间复杂度的确有些极限（用 #pragma 开挂的不算）。

通过观察前面的代码：

for (ll i=1;i<=n;i++)
{
    for (ll j=max(a[i].t,um[a[i].s]+k);j<min(1441LL,a[i].t+k);j++)
    {
            mac[j]++;
    } // 统计存在时间
    um[a[i].s]=a[i].t; // 更新时间
}

发现内层循环起到的就是一个循环加一的作用。我们很容易就可以联想到差分。这样时间复杂度就成功优化到了 O(n)（虽然在本题中秒数上并没有什么明显的变化，但是这题数据如果扩大到 5 \times 10^6 的话，这个优化就很吃香了）。

知周所众，前缀和是差分的逆运算。所以我们只需要最后对差分序列进行一次前缀和操作就可以得到上段代码中的 mac 数组。最后输出最大值即可。

最后的最后，献上 Code 2.0。

Code 2.0

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
struct exchange
{
    string s;
    ll t;
    bool operator<(const exchange &ech)const
    {
        return t<ech.t;
    }
}a[100010];
ll n,k,h,m,maca[1450],macb[1450],ans;
/*
maca 为原序列；macb 为差分序列。
其实仔细思考一下，maca 这个数组好像是可以去掉的，但是由于我太懒了，所以这件事就交给屏幕前的你啦~
*/
char c;
unordered_map<string,ll> um;
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>k;
    for (ll i=1;i<=n;i++)
    {
        cin>>a[i].s>>h>>c>>m;
        a[i].t=h*60+m+1;
    }
    sort(a+1,a+n+1);
    for (ll i=1;i<=n;i++)
    {
        if (max(a[i].t,um[a[i].s]+k)<=min(1441LL,a[i].t+k)) // 过滤非法情况
        {
            // 差分
            macb[max(a[i].t,um[a[i].s]+k)]++;
            macb[min(1441LL,a[i].t+k)]--;
        }
        um[a[i].s]=a[i].t;
    }
    for (ll i=1;i<=1440;i++)
    {
        maca[i]=maca[i-1]+macb[i]; // 前缀和得到原 mac 数组。
    }
    cout<<*max_element(maca+1,maca+1441);
    return 0; // 完结撒花~
}

end