题目大意:
给出n个数a[1..n],n<=262144,a[i]<=40,相邻且相同的数可以合并成一个并将值加1,问能获得的最大数是多少
用一个双向链表维护原数列,每个节点记录此节点对应的数值和数的个数,合并相邻且对应数值相同的节点
每次选一个数值最小的点处理,此时两侧的数都更大
若这个点只有一个数则直接删去并断开两侧,此时两侧的数不可能再互相合并
若这个点有偶数个数则数值+1,个数/2,检测能否和两侧合并
若这个点有奇数个数,两侧的数也不可能再互相合并了,因此将这个点分裂成两个互不相连的点,数值+1,(个数-1)/2,分别与两侧连接
可以证明时空复杂度均为O(n)
#include<cstdio>
#include<vector>
inline int input(){
int x=,c=getchar();
while(c>||c<)c=getchar();
while(c>&&c<)x=x*+c-,c=getchar();
return x;
}
const int N=;
std::vector<int>q[];
int nx[N],pv[N],v[N],t[N],p=,ans=,n;
int main(){
n=input();
for(int i=,a=-,b;i<=n;i++){
b=input();
if(a!=b)v[++p]=b;
++t[p];
a=b;
}
for(int i=;i<=p;i++){
pv[i]=i-;
nx[i]=i+;
q[v[i]].push_back(i);
}
nx[p]=;
for(int i=;i<;i++){
for(int j=,sz=q[i].size();j<sz;j++){
int w=q[i][j];
if(!t[w])continue;
if(t[w]==){
nx[pv[w]]=pv[nx[w]]=;
t[w]=;
}else if(t[w]&){
int _t=t[w]>>,_pv=pv[w],_nx=nx[w],_v=v[w]+;
t[w]=;
if(v[_pv]==_v){
t[_pv]+=_t;
pv[_nx]=nx[_pv]=;
}else{
nx[_pv]=++p;
pv[p]=_pv;
t[p]=_t;
v[p]=_v;
q[_v].push_back(p);
}
if(v[_nx]==_v){
t[_nx]+=_t;
pv[_nx]=nx[_pv]=;
}else{
pv[_nx]=++p;
nx[p]=_nx;
t[p]=_t;
v[p]=_v;
q[_v].push_back(p);
}
}else{
int _t=t[w]>>,_pv=pv[w],_nx=nx[w],_v=v[w]+;
t[w]=;
if(v[_pv]==_v){
if(v[_nx]==_v){
t[_pv]+=t[_nx]+_t;
t[_nx]=;
pv[nx[_pv]=nx[_nx]]=_pv;
}else{
t[_pv]+=_t;
pv[_nx]=_pv;
nx[_pv]=_nx;
}
}else if(v[_nx]==_v){
t[_nx]+=_t;
pv[_nx]=_pv;
nx[_pv]=_nx;
}else{
t[w]=_t;
v[w]=_v;
q[_v].push_back(w);
}
}
}
}
for(int i=;i<=p;i++)if(v[i]>ans)ans=v[i];
printf("%d",ans);
return ;
}