A. Powered Addition(二进制性质-思维)

\(拿样例来看1 7 6 5\)

\(6成长到7是最合理的，因为1s就可以实现而且对于后面来说最优\)

\(5成长到7是最合理的，因为2s就可以实现而且对于后面最优\)

\(发现了什么?二进制是可以组合成任意连续数的，而且每个数都倾向于成长到前面的最大数\)

\(只成长到前面最大的数有两个好处。\)

\(\color{Orange}{对后面最优，因为是满足条件的最小数字}\)

\(\color{Red}{耗费的秒数最小。因为是满足条件的最小数字，所以要增加的数字最小，需要的秒数也最小。}\)

#include <bits/stdc++.h>

using namespace std;

const int maxn=1e5+9;

int t,n,ans;

int a[maxn];

int main()

{

	cin>>t;

	while(t--)

	{

		cin>>n;

		for(int i=1;i<=n;i++)	cin>>a[i];

		int maxn=-1,last=a[1];

		for(int i=2;i<=n;i++)

		{

			if(a[i]<last)

				maxn=max(maxn,last-a[i]);

			else if(a[i]>last)

				last=a[i];

		}

		ans=0;

		if(maxn<0)	maxn=0;

		while(maxn)

		{

			maxn>>=1;

			ans++;

		}

		if(maxn==-1)	cout<<0<<endl;

		else cout<<ans<<endl;

	}

}

巴特西

A. Powered Addition(二进制性质-思维)

最新文章

热门文章