题意:
给你n个数,构造一组x,y,将这n个数划分为小于等于x,大于等于y以及大于x小于y的数三个区间,我们可以往每个区间添加数,使得每个区间的数为2的幂次,输出添加数的最小个数。
思路:
设num[x]为1-x中数的个数,我们枚举小于等于x的区间需要添加的2的幂次和大于x且小于y的2的幂次,那么剩下的部分自然就是大于等于y的数字个数,枚举求最小添加数。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
int a[200010],vis[200010],vis2[200010];
int Pow[30];
int FIND(int l,int r,int aim)
{
int pre = a[l-1];
while(l < r)
{
int mid = l+r+1>>1;
if(a[mid]-pre > aim)r = mid-1;
else l = mid;
}
return l;
}
int QPOW(int aa,int b)
{
int res = 1;
while(b)
{
if(b&1)res = res*aa;
aa*=aa;
b>>=1;
}
return res;
}
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
scanf("%d",&n);
int maxx = 0;
for(int i = 1; i <= n; i++)
{
scanf("%d",&a[i]);
maxx = max(maxx,a[i]);
vis[a[i]]++;
}
for(int i = 1; i <= n+3; i++)
{
a[i] = a[i-1]+vis[i];
}
int ans = 1e9;
for(int i = 0; i <= 18; i++)
Pow[i] = QPOW(2,i);
for(int i = 0; i <= 18; i++)
{
for(int j = 0; j <= 18; j++)
{
int l = FIND(0,n,QPOW(2,i));
int mid = FIND(l+1,n,QPOW(2,j));
int r = max(mid+1,n);
int k = lower_bound(Pow,Pow+19,a[r]-a[mid])-Pow;
int now_ans = (int)QPOW(2,i)-a[l]+(int)QPOW(2,j)-(a[mid]-a[l])+Pow[k]-(a[r]-a[mid]);
if(((int)QPOW(2,i)-a[l]<0) || ((int)QPOW(2,j)-(a[mid]-a[l])<0) || (Pow[k]-(a[r]-a[mid])<0))continue;
ans = min(ans,now_ans);
}
}
printf("%d\n",ans);
for(int i = 1; i <= n+3; i++)
a[i] =vis[i]= 0;
}
}