233
题目：题意：分析：代码：
题目：
传送门
题意：
给出
A
A
A、
B
B
B两个序列，有将
l
—
r
l—r
l—r区间内每个数先
+
1
+1
+1再
%
4
\%4
%4的操作，求将
A
A
A变为
B
B
B所要的最少步数
分析：
先出去模数操作，那么就是一道简单的差分约束，答案为
∑
i
=
1
n
p
[
i
]
−
p
[
i
−
1
]
\sum_{i=1}^np[i]-p[i-1]
∑i=1np[i]−p[i−1] 对于有模数时，我们考虑到对于区间
l
—
r
l—r
l—r进行操作时，结果更优的情况仅在
p
[
l
]
−
p
[
l
−
1
]
+
4
<
p
[
r
]
−
p
[
r
−
1
]
p[l]-p[l-1]+4<p[r]-p[r-1]
p[l]−p[l−1]+4<p[r]−p[r−1]时才会出现 所以我们对于这些特殊情况分类讨论
代码：
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#define LL long long
#define LZXANDME 1314
inline LL
read() {
LL d
=0,f
=1;char s
=getchar();
while(s
<'0'||s
>'9'){if(s
=='-')f
=-1;s
=getchar();}
while(s
>='0'&&s
<='9'){d
=d
*10+s
-'0';s
=getchar();}
return d
*f
;
}
using namespace std
;
int t
[5],p
[100005];
int main()
{
int q
=read();
while(q
--)
{
memset(t
,0,sizeof(t
));
int n
=read();
int ans
=0;
for(int i
=1;i
<=n
;i
++) p
[i
]=read();
for(int i
=1;i
<=n
;i
++) {int a
=read();p
[i
]=(a
-p
[i
]+4)%4;ans
+=max(p
[i
]-p
[i
-1],0);}
for(int i
=2;i
<=n
;i
++)
{
int c
=p
[i
]-p
[i
-1];
if(c
>0)
{
if(t
[1]&&c
>1) t
[1]--,t
[c
]++,ans
-=c
-1;
else if(t
[2]&&c
>2) t
[2]--,t
[c
]++,ans
-=c
-2;
}
else t
[c
+4]++;
}
printf("%d\n",ans
);
}
return 0;
}
