题意
思路
求出
a
i
a_i
ai表示还需多少才能转换成
b
i
b_i
bi，把它差分。 如果加的数不超过
4
4
4，那么答案就为
∑
i
=
1
n
m
a
x
(
0
,
a
i
)
\sum_{i=1}^{n}max(0,a_i)
∑i=1nmax(0,ai)。 否则如果让区间
(
l
,
r
]
(l,r]
(l,r]加上4，即
a
l
−
4
,
a
r
+
4
a_l-4,a_r+4
al−4,ar+4，那么就要使
a
r
+
4
<
a
l
a_r+4<a_l
ar+4<al，分类讨论。
代码
#include<cstdio>
int t
, n
, ans
;
int a
[100002];
int main() {
scanf("%d", &t
);
while (t
--) {
scanf("%d", &n
);
for (int i
= 1; i
<= n
; i
++)
scanf("%d", &a
[i
]);
int x
;
for (int i
= 1; i
<= n
; i
++) {
scanf("%d", &x
);
a
[i
] = (x
- a
[i
] + 4) % 4;
}
ans
= 0;
for (int i
= 1; i
<= n
; i
++) {
a
[i
] -= a
[i
+ 1];
if (a
[i
] > 0) ans
+= a
[i
];
}
int t2
= 0, t3
= 0;
for (int i
= 1; i
<= n
; i
++) {
if (a
[i
] == -3) {
if (t3
) {
t3
--;
ans
-= 2;
} else if (t2
) {
t2
--;
ans
--;
}
}
else if (a
[i
] == -2) {
if (t3
) {
t3
--;
t2
++;
ans
--;
}
}
else {
t2
+= a
[i
] == 2;
t3
+= a
[i
] == 3;
}
}
printf("%d\n", ans
);
}
}
