题解：P12836 [蓝桥杯 2025 国 B] 翻倍

· · 题解

题目大意

每次可以加倍一个元素，求最少多少次操作可以使序列不降。

首先肯定从前往后处理，不断加倍当前数知道大于等于上一个数。

这样做的问题在于数的大小会呈指数级爆炸增长，很容易就爆了 long long。

所以考虑另一种存储数的方式，将 a_i 化为 a_i = d \times 2^t 的形式。

由于 a_i > 0，此时比较两个数的大小只需要同时取对数 a_i < a_j \Leftrightarrow \log d_i + t_i < \log d_j + t_j。

至于加倍的最少次数这个是可以二分的。

考虑到 a_i < 2^{31} 故 d < 2^{31}，所以这样化下来的值域是不会炸的。

时间复杂度 \Theta(n \log^2 V)。

Code

#include <bits/stdc++.h>
#define int long long
#define umap unordered_map
#define vint vector<int>
#define ll long long
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define ull unsigned long long
#define uint unsigned int
#define rg register
#define il inline
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define sqr(x) ((x)*(x))
using namespace std;
const int INF=0x3f3f3f3f;
inline int read(){
    int w=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        w=(w<<1)+(w<<3)+(ch^48);
        ch=getchar();
    }
    return w*f;
}
inline void write(int x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9) write(x/10);
    putchar(x%10+'0');
}

const int N=2e5+10;
const double eps=1e-12;
int n,a[N],ans;
bool cmp(double a,double b){
    return fabs(a-b)<eps;
}
struct node{
    int d,t;
    node(int num){
        d=t=0;
        while(num%2==0) ++t,num/=2;
        d=num;
    }
    node(int _d,int _t){
        d=_d,t=_t;
    }
    node(){
        d=t=0;
    }
    friend bool operator <=(const node &a,const node &b){
        return ((1.0*log2(a.d)+1.0*a.t)<(1.0*log2(b.d)+1.0*b.t))||cmp((1.0*log2(a.d)+1.0*a.t),(1.0*log2(b.d)+1.0*b.t));
    }
}num[N];//d*2^t
signed main(){
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    #endif
    n=read();
    rep(i,1,n) a[i]=read(),num[i]=node(a[i]);
    for(int i=2;i<=n;++i){
        if(num[i-1]<=num[i]) continue;
        int l=1,r=1e18,res=-1;
        while(l<=r){
            int mid=(l+r)>>1;
            node x=node(num[i].d,num[i].t+mid);
            if(num[i-1]<=x){
                res=mid,r=mid-1;
            }
            else l=mid+1;
        }
        assert(res!=-1);
        ans+=res;
        num[i].t+=res;
    }
    write(ans);
    #ifndef ONLINE_JUDGE
    fprintf(stderr,"%f\n",1.0*clock()/CLOCKS_PER_SEC);
    #endif
    return 0;
}