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

本题我第一眼看着觉得很简单，这不就是模拟吗，每次给不满足

A_{i-1} \leq A_i

的元素乘二，知道满足就停止就可以了，

CPP

#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:

CPP

#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;
}

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

文章操作

相关推荐

评论

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