已严肃完成今日『P13010 【MX-X13-T5】「KDOI-12」茫茫人海如都市的晚高峰，迎面的车终将相遇，迎面的车终将分别。』大学习

· · 题解

乱水题的时候发现了校内大神 @rizynvu 出的题，肯定要来品尝一下。

为了保证文章阅读连贯性，建议读者即使知道题意也阅读一下本文内的题意。

题意

有 0,1 两个方向的车道，每个方向都有 1 条车道，除此之外还有 n 条动态车道，每条动态车道都可以花 C 天调整方向，在一开始动态车道的方向任意。

在 m 天中，第 i 天有 c_{i,j} 辆车往 j 方向行驶，请求出每天的车流量除以对应方向的车道数的 最大值的最小值。

数据范围：n\le 10^5，\sum m\le 5\times 10^5。

解法 1

看到题意中加粗的部分肯定本能想到二分答案。

二分一个答案 w，根据 w 我们可以算出每天所需的车道数 d_{i,j} 来保证 w 的合法性。

现在问题被转化为，第 i 天 j 方向需要有 d_{i,j} 条车道，问是否能够满足所有限制。

这其实是个还蛮经典的问题？然而我也不知道经典在哪里了。

进行观察，发现一个不知道有什么用的贪心性质，如果在 C 天内有同向的动态车道，直接拿来用肯定更好，毕竟它也转不到另一边去。

这条性质确实没啥用，但是反过来，如果有一条动态车道在 C 天内都没有被使用，我们就可以视其为一个任意方向的动态车道，我们称这样的车道为自由车道，在一开始我们有 n 条自由车道。

维护自由车道的数量，当自由车道不够补齐当前所需的车道就不合法，否则是合法的，于是这里的判定方式也就呼之欲出了：

代码写得可能更加清晰一些（大括号换行警告）：

:::info[代码]

#include<bits/stdc++.h>
using namespace std;
constexpr int N=500010;
int n,m,C;
int c[2][N],d[2][N];
deque<pair<int,int>>dq[2];
inline bool chk(double w)
{
    dq[0].clear(),dq[1].clear();
    int free=n,hav[2]={0,0};//自由车道数，目前实际车道数
    for(int i=1;i<=m;i++)
    {
        for(int j=0;j<=1;j++)
        {
            d[j][i]=ceil(c[j][i]/w)-1;
            if(!dq[j].empty()&&dq[j].front().first<i-C)
            {
                //当第 $i-C-1$ 天的车道数比第 $[i-C,i-1]$ 天的都要多时
                int c=dq[j].front().second;
                dq[j].pop_front();
                free+=c-dq[j].front().second;//多出来的这部分转化为自由车道
                hav[j]=dq[j].front().second;//实际所需的车道变少
            }
        }
        for(int j=0;j<=1;j++)
        {
            while(!dq[j].empty()&&dq[j].back().second<=d[j][i])dq[j].pop_back();
            //注意这里单调队列的维护顺序
            if(free<d[j][i]-hav[j])return false;
            free-=max(0,d[j][i]-hav[j]),hav[j]=max(hav[j],d[j][i]);
            //对应满足每天的车道限制
            dq[j].push_back(make_pair(i,d[j][i]));
        }
    }
    return true;
}
inline void solve()
{
    scanf("%d%d%d",&n,&m,&C);
    for(int i=1;i<=m;i++)scanf("%d",&c[0][i]);
    for(int i=1;i<=m;i++)scanf("%d",&c[1][i]);
    double l=0,r=1e9;
    for(int _=1;_<=77;_++)
    {
        double w=(l+r)/2;
        if(chk(w))r=w;
        else l=w;
    }
    printf("%.10lf\n",l);
    return;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)solve();
    return 0;
}

:::

由于单次判断使用单调队列是线性的，所以总时间复杂度是 \mathcal{O}(mT)，其中 T 为实数二分的次数。

解法 2

当我用二分答案过掉之后，@rizynvu 告诉我说这题其实可以线性。

仍然考虑二分答案转为判定问题，对于这个判定问题，有一个充要条件是 \forall 1\le i\le m-C,\max\limits_{j=i}^{i+C}d_{j,0}+\max\limits_{j=i}^{i+C}d_{j,1}\le n。

证明方法比较多样，比如上下界网络流、构造反证等，这里仅提供其中一种证法。

:::info[证明]

考虑前面的二分的判定过程，我们单调队列中记录了 \max\limits_{j=i}^{i+C}d_{j,0} 和 \max\limits_{j=i}^{i+C}d_{j,1}。

每当这两个值发生变化，变化的车道会全部转化为自由车道，我们可以将原做法中这里多出来的部分转化为自由车道改写为全部转化为自由车道再由新的两个最大值占用这些车道。

于是上述条件是充分的，满足上述条件判定即成功。

倒过来如果判定成功则该条件一定满足，否则一定有 d_{i,0}+d_{j,1}\gt n，由于 |i-j|\le C 所以一定不存在合法方案，其必要性应该较为显然。

证毕。

:::

利用此条件，我们仍然使用单调队列维护上述两个 \max，在每个位置取出最大值并讨论一下 d 的取值，这样的取值个数是 \mathcal{O}(1) 的，于是总的时间复杂度是 \mathcal{O}(m) 的。

:::info[代码]

#include<bits/stdc++.h>
using namespace std;
constexpr int N=500010;
int n,m,C;
int c[2][N];
deque<pair<int,int>>dq[2];
inline void solve()
{
    scanf("%d%d%d",&n,&m,&C);
    for(int i=1;i<=m;i++)scanf("%d",&c[0][i]);
    for(int i=1;i<=m;i++)scanf("%d",&c[1][i]);
    double ans=0;
    dq[0].clear(),dq[1].clear();
    for(int i=1;i<=m;i++)
    {
        for(int j=0;j<=1;j++)
        {
            while(!dq[j].empty()&&dq[j].front().first<i-C)dq[j].pop_front();
            while(!dq[j].empty()&&dq[j].back().second<=c[j][i])dq[j].pop_back();
            dq[j].push_back(make_pair(i,c[j][i]));
        }
        if(i>C)
        {
            double c[2]={dq[0].front().second,dq[1].front().second},res=1e9;
            int d[2];
            d[0]=floor((n+2)/(c[0]+c[1])*c[0]);
            d[1]=n+2-d[0];
            if(d[0]&&d[1])res=min(res,max(c[0]/d[0],c[1]/d[1]));
            d[0]++,d[1]--;
            if(d[0]&&d[1])res=min(res,max(c[0]/d[0],c[1]/d[1]));
            ans=max(ans,res);
        }
    }
    printf("%.10lf\n",ans);
    return;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)solve();
    return 0;
}

:::

代码甚至比二分答案的更加简短。

Bonus

@rizynvu 还给我说，这题原题是给出 d，有 q 次修改，每次将某个 d 加减 1，由于需要压难度所以改成了现在这样。

反正我是懒得想了，@rizynvu 怎么这么强。