The Longest Straight FZU - 2216 二分
The Longest Straight FZU - 2216
二分求解
题意
有n张卡片,每个卡片代表了从1到M的一个数字(可能重复), 这n个卡片中还可能有零,可以用来代表任何从1到M的数字,求最长的连续序列是多少
分析
1 先建立数组, 若在i的位置有一个卡片, 则标记为真,
2 然后用sum数组记录从1到i总共有多少个空缺,
3 再用一个left数组记录每一段已经有卡片的最左边的数字,
4 然后对于每一个left,从left[i] 到 M 二分求最大值, 即求从left[i]开始的最长序列是多少(需要增加一个1,因为可能从1开始)
参考代码
const int LEN = 123456;
int sum[LEN];
int ar[LEN];
int Left[LEN];
int maxlen;
int N,M;
void check(int x,int zero)//从x到M的最长序列是多少
{
if(!ar[x])
zero--;
// if(x+zero>=M)
// {
//maxlen = max(maxlen,M-x+1);
// return ;
// }
int spaces = sum[M]-sum[x];
if(zero>=spaces)////如果从x到M的空缺数量小于0卡片的数量,
//最长序列就是M-x+1
{
maxlen = max(maxlen,M-x+1);
return ;
}
int l = x,r = M;//否则进行二分操作
while(r-l>1)
{
int mid = l+(r-l)/2;
if(sum[mid]-sum[x]==zero)
l = mid;
else if(sum[mid]-sum[x]>zero)
r = mid-1;
else if(sum[mid]-sum[x]<zero)
l = mid+1;
}
if(sum[r]-sum[x]==zero)
maxlen = max(maxlen,r-x+1);
else
maxlen = max(maxlen,l-x+1);
}
int main(void)
{
int T;
cin>>T;
while(T--)
{
maxlen = 0;
me(ar);
me(sum);
me(Left);
cin>>N>>M;
int Zero = 0;
while(N--)
{
int a;
scanf("%d",&a);
if(a==0)
++Zero;
else
ar[a] = 1;
}
ar[0] = 1;
bool sign = false;
int num = 1;
for(int i = 1; i <= M; ++i)
{
sum[i] = sum[i-1] + !ar[i];
if(!sign&&ar[i])
{
Left[num++] = i;
sign = true;
}
if(sign&&!ar[i])
sign=false;
}
check(1,Zero);//可能从1开始
for(int i = 1; i < num; ++i)
{
check(Left[i],Zero);
}
cout<<maxlen<<endl;
}
return 0;
}
锐捷网络股份有限公司公司福利 348人发布
