专栏文章

[CF2157E] Adjusting Drones 题解

aaeiouaoeiu
CF2157E题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min1x4tw
此快照首次捕获于
2025/12/01 19:13
3 个月前
此快照最后确认于
2025/12/01 19:13
3 个月前
查看原文
首先 aa 的顺序没啥用，若设 bb 为 aa 的桶，则我们只关心是否有 bx>kb_x>k，操作时也只会根据 bb 的情况来改变 bb。
观察一次操作时 bb 如何改变，可以看作每个 bib_i 都拿出了 bi−1b_i-1 这一部分，挪到了 bi+1b_{i+1}。
这样就很像一个技巧型 dp 了，但是这里介绍一个力大砖飞做法。
首先 bib_i 只有挪到一个 00 上面才会使得值 −1-1，同时会在挪到的所有 00 上留下 11，这启示我们每次都跳到下一个 00，对操作进行压缩。
进行操作后 max⁡bi\max b_i 只减不增，于是答案具有单调性，可以二分。
若要检查 xx，则从右往左检查，每次让 bib_i 不断往右边的 00 跳，直到操作次数 >x>x，此时检查 bib_i 是否已经跳了至少 bi−kb_i-k 次，然后将跳过的 00 用并查集合并在一起，这样就可以快速找下一个 00 了。
时间复杂度 O(nlog⁡nα(n))\mathcal{O}(n\log n\alpha(n))。
codeCPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...