My Blogs
[ARC182D] Increment Decrement Again
判掉 $m=2$。接下来有个奇妙的转化：看成 $A$ 不对 $m$ 取模，要求变为 $\forall i<n,\lvert a_i-a_{i+1}\rvert<m\wedge a_i\not= a_{i+1}$。
然后发现 $a$ 的大小关系是不会变的，所以如果固定了 $a’1$，则后面的都是固定的。可以先令 $a’_1=b_1$，根据大小关系求出任意一组合法的 $a’$，接下来问题变为最小化 $\sum{i=1}^n\lvert a_i-a’_i-km\rvert$，可以二分类似找中位数的方法解决。复杂度 $\mathcal O(n\log n\log V)$。
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
int n,m,L,R,mid,p,a[200010],b[200010],c[200010];
inline void mian()
{
read(n,m);
for(int i=1;i<=n;++i)read(a[i]);
for(int i=1;i<=n;++i)read(b[i]);
if(m==2){if(a[1]==b[1])puts("0");else puts("-1");return;}
c[1]=b[1];
for(int i=2;i<=n;++i)
{
int val=(b[i]-b[i-1]+m)%m;
if(a[i]>a[i-1])c[i]=c[i-1]+val;
else c[i]=c[i-1]+val-m;
}
for(int i=1;i<=n;++i)c[i]=a[i]-c[i];
sort(c+1,c+1+n),L=-1000*inf,R=1000*inf;
while(L<R)
{
mid=L+((R-L+1)>>1),p=lower_bound(c+1,c+1+n,mid*m)-c;
if(p<=(n+1)/2)L=mid;
else R=mid-1;
}
int ans=0,s=0;
for(int i=1;i<=n;++i)ans+=abs(c[i]-L*m);
for(int i=1;i<=n;++i)s+=abs(c[i]-(L+1)*m);
write(min(ans,s));
}