CF819B&CF820D 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 p1, p2, ... pn,
k = 1: shift pn, p1, ... pn - 1,
...,
k = n - 1: shift p2, p3, ... pn, p1.

Input

First line contains single integer n (2 ≤ n ≤ 106) — the length of the permutation.

The second line contains n space-separated integers p1, p2, ..., pn (1 ≤ pi ≤ n) — the elements of the permutation. It is guaranteed that all elements are distinct.

Output

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.

题解

对于一个数(i)，越往第(i)个这个位置靠近，差值越小，相反差值越大。
于是我们考虑记录转变的时间，在不变的时候，一直可以保证它的单调性，每次往答案里(+1)或者(-1)就可以，然后O(n)去更新，最后记得从n到1时的变化要单独更新。
更详细的看代码把。

代码

#include<iostream>
#include<cstdio>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=1e6+10;
int cnt[maxn];
int a[maxn],n;
int abs(int x){return x>0?x:-x;}
int main(){
    ios::sync_with_stdio(false);
    while(cin>>n){
        int add=0,sub=0,b=0;
        long long tmp=0,res;
        memset(cnt,0,sizeof(cnt));
        for(int i=1;i<=n;i++){
            cin>>a[i];
            tmp+=abs(a[i]-i);
            cnt[(a[i]-i+n)%n]++;//记录第几次移动后单调性会变
            if(a[i]>i)sub++;
            else add++;
        }
        res=tmp;
        for(int i=1;i<n;i++){
            tmp+=add-sub-1;//减去从n到1的那个数对答案的贡献，然后单独计算
            tmp+=(a[n-i+1]-1)-(n-a[n-i+1]);//加上从n到1的那个数在第1个位置时的贡献，减去它在第n个位置时的贡献
            sub=sub-cnt[i]+1;//经过转折点的数会从对答案每次贡献-1变成+1，于是要减去这些数，同时由于最后一个数本来是加1的，变成第一个会变成-1的贡献，所以sub要+1
            add=add+cnt[i]-1;//同上（注意1在不是第一个位置的情况下都是+1，所以上述是成立的）
            if(res>tmp){
                res=tmp;
                b=i;
            }
        }
        cout<<res<<" "<<b<<endl;
    }
}