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

健美猫"/>

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

文章目录

• • • • R e s u l t Result Result
      • H y p e r l i n k Hyperlink Hyperlink
      • D e s c r i p t i o n Description Description
      • S o l u t i o n Solution Solution
      • C o d e Code Code

R e s u l t Result Result

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

H y p e r l i n k Hyperlink Hyperlink

以前那种做法的题解
YbtOj

D e s c r i p t i o n Description Description

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

数据范围： n ≤ 2 × 1 0 6 n\leq 2\times 10^6 n≤2×106

S o l u t i o n Solution 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

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

而 s i ≥ i s_i\geq i si​≥i的部分，是跟上面一样的，没有影响

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

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

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

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

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

C o d e Code 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);
}