[Aug17] Rotate

场上一点思路都没有真难受

题意

有一个长度为n,在模4域下的序列。一次操作可以使一段区间加1。求使这个序列变成另一个给定序列的操作最小次数。

思路

(感谢pobiren巨爷的倾情讲解)

首先将目标序列减原序列,得到在模4域下的序列,我们要不断减1使其变成0。

我们对序列差分,$ c[i] = a[i] - a[i - 1] $ 。

然后我们可以知道,在不对序列某些区间进行加4操作时,结果就是 $ \sum{max\{c[i],0\}} $ 。

然后考虑对某些区间加4使答案更优。

这样会使 $ c[l] $ 减4, $ c[r] $ 加4。

$ c[l] = 0 $ 或 $ c[l] = -1 $ 时加1不能得到更优解。

$ c[l] = -2 $ 时 $ c[r] = 3 $ 则答案减1。

$ c[l] = -3 $ 时 $ c[r] = 3 $ 则答案减2,$ c[r] = 2 $ 则答案减1。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
inline int getint()
{
int r = 0,s = 1;char c = getchar();for(;!isdigit(c);c = getchar()) if(c == '-') s = 0;
for(;isdigit(c);c = getchar()) r = (((r << 2) + r) << 1) + (c ^ '0');return s ? r : -r;
}
const int N = 100010;
int n,c[N],ans = 0,cnt[10];
int main()
{
n = getint();
for(int i = 1;i <= n;++i) c[i] = getint();
for(int i = 1;i <= n;++i) c[i] = (getint() - c[i] + 4) % 4;
for(int i = n;i;--i) c[i] -= c[i - 1];
for(int i = 1;i <= n;i++) ans += std::max(c[i],0);
for(int i = 1;i <= n;i++)
{
if(c[i] == 3)
{
if(cnt[1]) cnt[1]--,ans -= 2;
else if(cnt[2]) cnt[2]--,ans--;
}
else if(c[i] == 2 && cnt[1]) cnt[1]--,ans--;
else if(c[i] < 0) cnt[c[i] + 4]++;
}
printf("%d\n",ans);
return 0;
}