YbtOj NOIP2020 模拟赛 B 组 Day9 T2 序列旋转 JZOJ 5343.健美猫

$Result$

下面的是今天比赛的时候写出来，上面是两年前写出来的【当时没交】

$Hyperlink$

以前那种做法的题解
YbtOj

$Description$

一个序列$s_i$，试着旋转这个序列（即下标$i$变成$i-1$，$1$变成$n$）
最小化${\sum }_{i=1}^n|s_i-i|$
输出这个最小值

数据范围：$n\le 2\times 10^6$

$Solution$

两年前的做法是考虑旋转下标带来的影响，这里不再具体提
今天比赛时的想法是考虑对每种下标的答案

例如样例二（第一行），及其可能的六个下标序列（第二行至第七行）【编号为一到六】
4 2 2 4 2 5
1 2 3 4 5 6
6 1 2 3 4 5
5 6 1 2 3 4
4 5 6 1 2 3
3 4 5 6 1 2
2 3 4 5 6 1

容易发现，如果我们不考虑绝对值，答案显然就是$\sum s_i-\sum i$，记为$sum$，接下来考虑没有正确计算的部分

而$s_i\ge i$的部分，是跟上面一样的，没有影响

$s_i<i$的部分，正确答案应该是$i-s_i$，而我们会算成$s_i-i$，这样我们就少算了$2(i-s_i)$的贡献，考虑维护这个贡献即可

而$s_i<i$的部分，在下标序列中是一段连续的值，显然$s_i$对它的贡献会是一个单调下降序列

例如上述样例中的第一个数4，它会对第二个下标序列到第四个下标序列分别有2,1,0（实际上要乘二，为了方便最后再乘）的贡献

第二个数2，它会对第三个下标序列到第六个下标序列分别由4,3,2,1的贡献（同上，最终要除以二）

二阶差分+前缀和即可处理，时间复杂度$O(n)$

$Code$

#include<cctype>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;int n,a,up,down;
LL sum,s[2000010],bj[2000010],b[2000010],ans=1e18;
inline LL read()
{char c;LL d=1,f=0;while(c=getchar(),!isdigit(c)) if(c=='-') 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()
{n=read();for(register int i=1;i<=n;i++){a=read();sum+=a-i;if(a==n) continue;down=(n-a+i)%n;if(down==0) down=n;up=down-(n-a-1);//up和down是求出这次操作影响的下标序列的区间，如果up<=0，说明有两段if(up>0){s[up]+=n-a;bj[up+1]--;bj[down+2]++;//只有一段的话，直接更新即可continue;}s[1]+=i-a;bj[2]--;bj[down+2]++;//上面那段是1~downs[n+up]+=n-a;bj[n+up+1]--;bj[n+2]++;//下面那段是n+up~n【因为up此时是负数】}for(register int i=1;i<=n;i++){bj[i]+=bj[i-1];s[i]+=s[i-1]+bj[i];//bj先做前缀和，s再做前缀和ans=min(ans,s[i]*2);}printf("%lld",ans+sum);
}