📅 发布时间：2026/6/19 16:35:32

CF819B Mister B and PR Shifts

题目描述

Some time ago Mister B detected a strange signal from the space, which he started to study.

After some transformation the signal turned out to be a permutation $ p $ of length $ n $ or its cyclic shift. For the further investigation Mister B need some basis, that's why he decided to choose cyclic shift of this permutation which has the minimum possible deviation.

Let's define the deviation of a permutation $ p $ as .

Find a cyclic shift of permutation $ p $ with minimum possible deviation. If there are multiple solutions, print any of them.

Let's denote id $ k $ ( $ 0<=k<n $ ) of a cyclic shift of permutation $ p $ as the number of right shifts needed to reach this shift, for example:

$ k=0 $ : shift $ p_{1},p_{2},...\ p_{n} $ ,
$ k=1 $ : shift $ p_{n},p_{1},...\ p_{n-1} $ ,
...,
$ k=n-1 $ : shift $ p_{2},p_{3},...\ p_{n},p_{1} $ .

输入格式

First line contains single integer $ n $ ( $ 2<=n<=10^{6} $ ) — the length of the permutation.

The second line contains $ n $ space-separated integers $ p_{1},p_{2},...,p_{n} $ ( $ 1<=p_{i}<=n $ ) — the elements of the permutation. It is guaranteed that all elements are distinct.

输出格式

Print two integers: the minimum deviation of cyclic shifts of permutation $ p $ and the id of such shift. If there are multiple solutions, print any of them.

输入输出样例 #1

输入 #1

3
1 2 3

输出 #1

0 0

输入输出样例 #2

输入 #2

3
2 3 1

输出 #2

0 1

输入输出样例 #3

输入 #3

3
3 2 1

输出 #3

2 1

说明/提示

In the first sample test the given permutation $ p $ is the identity permutation, that's why its deviation equals to $ 0 $ , the shift id equals to $ 0 $ as well.

In the second sample test the deviation of $ p $ equals to $ 4 $ , the deviation of the $ 1 $ -st cyclic shift $ (1,2,3) $ equals to $ 0 $ , the deviation of the $ 2 $ -nd cyclic shift $ (3,1,2) $ equals to $ 4 $ , the optimal is the $ 1 $ -st cyclic shift.

In the third sample test the deviation of $ p $ equals to $ 4 $ , the deviation of the $ 1 $ -st cyclic shift $ (1,3,2) $ equals to $ 2 $ , the deviation of the $ 2 $ -nd cyclic shift $ (2,1,3) $ also equals to $ 2 $ , so the optimal are both $ 1 $ -st and $ 2 $ -nd cyclic shifts.

解题报告

这里其实有个小小的套路：看到绝对值，一般都要按正负数进行分类讨论。

先说一下，这题作者是在本校的小测中的写的，在小测中本题被改成了左移，所以以下的讨论是对于左移而言的，最后再用对称性转换回来。

现在考虑已经进行了 $k-1$ 次左移，正在进行第 $k$ 次左移。

若不考虑绝对值，除了第一项，每一个 $p_i$ 的贡献会从 $p_i-i$ 变到 $p_i-(i-1)$，而第一项 $p_1$ 的贡献会从 $p_1-1$ 变为 $p_1-n$。

现在加上绝对值，进行分类讨论：

第一项比较特殊，我们单独考虑其变化，就是 $|p_1-n|-|p_1-1|$。
当 $i\neq 1$，如果 $p_i-i < 0$，那么 $|p_i-(i-1)|-|p_i-i|=-1$。
当 $i\neq 1$，如果 $p_i-i \geq 0$，那么 $|p_i-(i-1)|-|p_i-i|=1$。

那么设第 $k$ 次左移后的 $\sum_{i=1}^{n} |p_i-i|$ 为 $ans_{k}$，左移前的 $p_i-i < 0$ 的个数为 $cnt_1$，$p_i-i \geq 0$ 的个数为 $cnt_2$，那么就有以下递推关系：

\[ans_{k}=ans_{k-1}+(|p_1-n|-|p_1-1|)-cnt_1+cnt_2-1 \]

这里行末的 $+1$ 是因为肯定有 $p_1-1\geq0$，那么它会包含进 $cnt_2$，所以会多个 $+1$，需要减回来。

那么现在的问题就是正确维护每一次左移前的 $cnt_1$ 和 $cnt_2$。考虑对原数列进行了第 $k$ 次左移和第 $k-1$ 次左移负数和正数的个数的变化，那么：

对于每个 $p_i$，在第 $i$ 次时会被移到最后，若 $p_i \neq n$，肯定有 $p_i-1\geq0$ 且 $p_i-n < 0$。
如果 $p_i \leq i$，若 $p_i \neq n$，在第 $i-p_i$ 次时会变成正数。
如果 $p_i > i$，若 $p_i \neq n$，在第 $i$ 次时会被移到最后，然后再左移第 $n-p_i$ 次时会变成正数。
如果 $p_i=n$，一直有 $p_i-i \geq 0$。

这样就可以正确维护了，同时 $k$ 次左移相当于 $n-k$ 次右移。

复杂度 $O(n)$，代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int INF=0x3f3f3f3f;
const int N=2001100;#define ckmax(x,y) ( x=max(x,y) )
#define ckmin(x,y) ( x=min(x,y) )inline int read()
{int f=1,x=0; char ch=getchar();while(!isdigit(ch)) { if(ch=='-') f=-1; ch=getchar(); }while(isdigit(ch))  { x=x*10+ch-'0';    ch=getchar(); }return f*x;
}int n;
int w[N<<1];
int d[N][2];inline void debug()
{for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){int pos=i-j+1;if(pos<=0) pos+=n;cout<<w[i]-pos<<" ";}cout<<endl;}
}signed main()
{n=read();for(int i=1;i<=n;i++)w[i+n]=w[i]=read();int ans=0,tmp=0,K=n;for(int i=1;i<=n;i++){d[i][0]++,d[i][1]--;if(w[i]>i) d[i+n-w[i]][0]--,d[i+n-w[i]][1]++;else d[i-w[i]][0]--,d[i-w[i]][1]++;}int cnt1=0,cnt2=0;for(int i=1;i<=n;i++){ans+=abs(w[i]-i);cnt1+=w[i]<i;cnt2+=w[i]>=i;}tmp=ans;for(int i=1;i<n;i++){tmp-=abs(w[i]-1)-abs(w[i]-n);tmp-=cnt1,tmp+=cnt2,tmp--;cnt1+=d[i][0],cnt2+=d[i][1];if(tmp<ans) K=i;ckmin(ans,tmp);}printf("%lld %lld",ans,n-K);return 0;
}