[EC Final 2021] Prof. Pang and Ants

· · 题解

考虑二分答案 t，求出在 t 个时刻内最多能有多少只蚂蚁。

对于一个洞口，一定是先放出一些蚂蚁，再接进一些蚂蚁。

可以发现，对于第 i 个洞口，出去的第 j 只蚂蚁到达冰箱的时间是 a_i+j，接进来的倒数第 j 只蚂蚁要在 t-j-a_i 时刻前到达冰箱。

假如我们已经知道每个洞口出去和进来了多少只蚂蚁，那么就变成了一个二分图匹配问题。

因为每个洞口出去和进来的蚂蚁本质是相同的，所以我们会让前一半的时间出蚂蚁，后一半的时间进蚂蚁。

那么在 t 是奇数的时候中间的时刻不好决定，因此我们改成每个时刻可以进去或出来 2 只蚂蚁，中间时刻 1 进 1 出，最后答案除以 2。

直接做二分图匹配是不行的，但发现每个左部点连接的都是右部的一个后缀，因此从前到后扫 t 个时刻，每次直接贪心的匹配所有可以匹配的右部点。

这样每次是 O(t) 的，但注意到每个时刻新加入的左部点数量和右部点数量的变化次数是 O(n) 的，于是可以离散化后对于数量相同的一起处理。

时间复杂度 O(n\log n\log V)，常数较大，但因为有 8s 的时限可以通过。

注意到每个函数的形状是相同的，所以可以提前将 a_i 排好序后归并几种端点，时间复杂度 O(n(\log n+\log V))。

这里只实现了 O(n\log n\log V) 的代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int T,n,a[N],cp;
ll m;
struct opt{
    ll x;int t,c;
    bool operator <(const opt b)const{return x<b.x;}
}p[N*6];
bool check(ll t){
    cp=0;
    ll h=t>>1;
    for(int i=1;i<=n;++i){
        if(t&1){
            p[++cp]={a[i]+1,0,2};
            p[++cp]={a[i]+h+1,0,-1};
            p[++cp]={a[i]+h+2,0,-1};
            p[++cp]={h-a[i],1,1};
            p[++cp]={h-a[i]+1,1,1};
            p[++cp]={t-a[i],1,-2};
        }else{
            p[++cp]={a[i]+1,0,2};
            p[++cp]={a[i]+h+1,0,-2};
            p[++cp]={h-a[i],1,2};
            p[++cp]={t-a[i],1,-2};
        }
    }
    ll sf=0,st=0,res=0,rs=0;
    sort(p+1,p+cp+1);
    for(int i=1;i<cp;++i){
        if(!p[i].t)sf+=p[i].c;
        else st+=p[i].c;
        ll dt=p[i+1].x-p[i].x;
        if(!dt)continue;
        if(sf>=st)res+=st*dt,rs+=(sf-st)*dt;
        else{
            rs+=sf*dt;
            ll u=min(st*dt,rs);
            rs-=u,res+=u;
        }
    }
    return res>=m*2;
}
void solve(){
    scanf("%d%lld",&n,&m);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    ll l=2*m/n,r=2.1e14;
    while(l<r){
        ll mid=l+r>>1;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    printf("%lld\n",l);
}
int main(){
    scanf("%d",&T);
    while(T--)solve();
    return 0;
}