题解：P12642 [KOI 2024 Round 1] 加倍

songyouyi · 2025-05-29 08:28:21 · 题解

本题我第一眼看着觉得很简单，这不就是模拟吗，每次给不满足 A_{i-1} \leq A_i 的元素乘二，知道满足就停止就可以了，

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[250010];
signed main()
{
    int n;
    scanf("%lld",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    int ret=0;
    for (int i=2;i<=n;i++)
    {
        //模拟
        while (a[i]<a[i-1])
        {
            a[i]*=2;
            ret++;
        }
    }
    printf("%lld",ret);
    return 0;
}

结果交上去一看 33 TLE，而且这种做法会爆 longlong，极限数据最后一项可能会非常大，于是我们想到二分，至于改成升序后的数组太大的问题，我们可以不直接记录改为升序后的数组的值，可以直接记录它的每一项乘了多少个二，我们通过与上一次乘的数比较一下，但直接比较会爆 longlong，我们注意到他们乘的数都是 2 的幂次，所以其中一个数必然是另外一个数的倍数，我们可以判断一下，如果这两个数相差太大就跳过，然后我们用这两个数的商乘原来乘的更大的那个数，然后再比较，这样就可以避免爆 longlong 问题。

AC Code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[250010];
int cheng[250010];
int k[110];
signed main()
{
    int n;
    scanf("%lld",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    int ret=0;
    k[1]=2;
    k[0]=1;
    //预处理2的幂次 
    for (int i=2;i<=50;i++)
    {
        k[i]=k[i-1]*2;
    }
    for (int i=2;i<=n;i++)
    {
        int l=0,r=1e9,best=-1;
        //二分 
        while (l<=r)
        {
            int mid=(l+r)/2;
            //相差太大就退出 
            if (mid-cheng[i-1]>=40)
            {
                r=mid-1;
                continue;
            }
            if (cheng[i-1]-mid>=40)
            {
                l=mid+1;
                continue;
            }
            int now,last;
            //爆longlong问题处理 
            if (cheng[i-1]>=mid)
            {
                now=a[i];
                last=a[i-1]*k[(cheng[i-1]-mid)];
            }
            else
            {
                now=a[i]*k[(mid-cheng[i-1])];
                last=a[i-1];
            }
            if (now>=last)
            {
                best=mid;
                r=mid-1;
            }
            else
            {
                l=mid+1;
            }
        }
        ret+=best;
        cheng[i]=best;
    }
    printf("%lld",ret);
    return 0;
}