Powered Addition

题意

给出n个数字，现在你可以在第x秒，选择任意数量的下标，让这些位置上的数加上\(2^{x-1}\)，问最快需要几秒使得数列变成一个非递减的序列。

思路

让求x的最小值，转换一下。

假设第i个数字在x秒内加的权值为val[i]，x的最小值即让val[i]最大值最小。

如何最小，如果a[i-1]>a[i]，就让a[i]=a[i-1]，计算它们差值的二进制最高位，取最大值。

代码

//#include<bits/stdc++.h>

#include<vector>

#include<stdio.h>

#include<algorithm>

#include<string.h>

#include<string>

#include<math.h>

#include<queue>

#include<map>

#define pb push_back

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int N=1e6+10;

const int mod=1e9+7;

const ll inf=0x3f3f3f3f3f3f3f3f;

const double eps=1e-14;

ll arr[N];

int main()

{

    ll T;

    scanf("%lld",&T);

    while(T--)

    {

        ll n;

        scanf("%lld",&n);

        for(ll i=1;i<=n;i++)

            scanf("%lld",&arr[i]);

        ll ans=0,maxn=-inf;

        for(ll i=1;i<=n;i++)

        {

            ll cnt=0;

            if(arr[i]<maxn)

            {

                ll dis=maxn-arr[i];

                while(dis)

                {

                    dis/=2;

                    cnt++;

                }

            }

            maxn=max(maxn,arr[i]);

            ans=max(ans,cnt);

        }

        printf("%lld\n",ans);

    }

    return 0;

}

博客

巴特西

CF#633 C. Powered Addition 思维

Powered Addition

题意

思路

代码

最新文章

热门文章