D
e
s
c
r
i
p
t
i
o
n
Description
Description
给定一个长度为
n
n
n的序列
A
A
A，每次可以选择一个区间
[
l
∼
r
]
[l\sim r]
[l∼r]使得
(
A
i
+
+
)
m
o
d
4
(
i
∈
[
l
∼
r
]
)
(A_i++)mod\ 4(i\in [l\sim r])
(Ai++)mod 4(i∈[l∼r])，问使
A
A
A序列变成
B
B
B序列的最小步数
数据范围：
n
≤
1
0
5
n\leq 10^5
n≤105
S
o
l
u
t
i
o
n
Solution
Solution
首先如果不考虑
m
o
d
mod
mod的情况就是积木大赛了
考虑
m
o
d
mod
mod的话我们计算+4的情况带来的优化即可
时间复杂度：
O
(
n
)
O(n)
O(n)
C
o
d
e
Code
Code
#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std
;int a
[100002],t
,n
,t2
,t3
;
long long ans
;
inline long long read()
{
char c
;int d
=1;long long f
=0;
while(c
=getchar(),!isdigit(c
))if(c
==45)d
=-1;f
=(f
<<3)+(f
<<1)+c
-48;
while(c
=getchar(),isdigit(c
)) f
=(f
<<3)+(f
<<1)+c
-48;
return d
*f
;
}
signed main()
{
t
=read();
while(t
--)
{
n
=read();ans
=0;t2
=t3
=0;
for(register int i
=1;i
<=n
;i
++) a
[i
]=read();
for(register int i
=1,x
;i
<=n
;i
++)
{
x
=read();
a
[i
]=(x
-a
[i
]+4)%4;
}
for(register int i
=1;i
<=n
;i
++) a
[i
]-=a
[i
+1],ans
+=max(a
[i
],0);
for(int i
=1;i
<=n
;i
++)
{
if(a
[i
]==3) t3
++;else
if(a
[i
]==2) t2
++;else
if(a
[i
]==-2)
{
if(t3
)
{
t3
--;
t2
++;
ans
--;
}
}
else
if(a
[i
]==-3)
{
if(t3
)
{
t3
--;
ans
-=2;
}
else
if(t2
)
{
t2
--;
ans
--;
}
}
}
printf("%d\n",ans
);
}
}
