[CF2157E] Adjusting Drones 题解

· · 题解

首先 a 的顺序没啥用，若设 b 为 a 的桶，则我们只关心是否有 b_x>k，操作时也只会根据 b 的情况来改变 b。

观察一次操作时 b 如何改变，可以看作每个 b_i 都拿出了 b_i-1 这一部分，挪到了 b_{i+1}。

这样就很像一个技巧型 dp 了，但是这里介绍一个力大砖飞做法。

首先 b_i 只有挪到一个 0 上面才会使得值 -1，同时会在挪到的所有 0 上留下 1，这启示我们每次都跳到下一个 0，对操作进行压缩。

进行操作后 \max b_i 只减不增，于是答案具有单调性，可以二分。

若要检查 x，则从右往左检查，每次让 b_i 不断往右边的 0 跳，直到操作次数 >x，此时检查 b_i 是否已经跳了至少 b_i-k 次，然后将跳过的 0 用并查集合并在一起，这样就可以快速找下一个 0 了。

时间复杂度 \mathcal{O}(n\log n\alpha(n))。

::::info[code]

#include<bits/stdc++.h>
#define pb emplace_back
#define pob pop_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
const ll maxn=1000007,ee=1e18;
ll n,k,a[maxn],b[maxn],f[maxn],ans;
struct Dsu{
    ll fa[maxn],siz[maxn],l[maxn],r[maxn];
    void init(ll n){
        iota(fa+1,fa+1+n,1),fill(siz+1,siz+1+n,1);
        iota(l+1,l+1+n,1),iota(r+1,r+1+n,1);
    }
    ll fid(ll x){for(;x!=fa[x];x=fa[x]=fa[fa[x]]); return x;}
    void merge(ll x,ll y){
        ll fx=fid(x),fy=fid(y);
        if(fx==fy) return;
        if(siz[fx]>siz[fy]) swap(fx,fy);
        siz[fy]+=siz[fx];
        l[fy]=min(l[fy],l[fx]),r[fy]=max(r[fy],r[fx]);
        fa[fx]=fy;
    }
}dsu;
bool check(ll x){
    dsu.init(4*n);
    for(ll i=2*n,cur,p,to;i>=1;i--){
        cur=b[i],p=i;
        for(ll j=0;;){
            if(cur<=1) break;
            dsu.merge(p,p+1);
            to=dsu.r[dsu.fid(p)];
            j+=to-p,p=to;
            if(j>x) break;
            cur--;
        }
        if(b[i]) dsu.merge(p,p+1);
        if(cur>k) return 0;
    }
    return 1;
}
ll solve(void){
    for(ll l=0,r=3*n,mid;l<=r;){
        mid=(l+r)>>1;
        if(check(mid)) ans=mid,r=mid-1;
        else l=mid+1;
    }
    return ans;
}
int main(void){
    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll T=1; cin>>T;
    for(;T--;){
        cin>>n>>k,ans=0;
        for(ll i=1;i<=2*n;i++) b[i]=0;
        for(ll i=1;i<=n;i++) cin>>a[i],b[a[i]]++;
        cout<<solve()<<"\n";
    }
    return 0;
}

::::