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 (Sigma^{i=n}_{i=1}|p[i]-i|).

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 ≤ 106)) — 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

3
1 2 3

输出１

0 0

输入2

3
2 3 1

输出2

0 1

输入33

3
3 2 1

输出3

2 1

题解

如果纯模拟, 真的移动(n)次, 再加起来计算最小值, 复杂度太高, 需要一个(O(n))的方法

很显然, 每次移动一位, 下标之间相差1, 可以看出规律来, 就是(p[i])不变, 每次(i)增加(1), 超出范围的置为(1),

(p[i] < i)时, 随着移动, (i)逐渐变大, (|p[i] - i|=i-p[i])逐渐变大, 当(i)超过(n)时, 重置为(1), 有可能变成第二种状态

(p[i] > i)时, 随着移动, (i)逐渐变大,(|p[i] - i|=p[i] - i)逐渐变小, 当移动到(p[i] = i)时, 转为第三种状态, 先记录下来(p[i])与(i)最初的距离, 当移动次数与距离相等时, 转换状态

(p[i] = i)时, (|p[i] - i|=0), 再移动将会转为第一种状态.

最开始计算出所有数字之和, 根据移动次数, 处于三个状态的数字个数即可直接计算出现在的(Sigma^{i=n}_{i=1}|p[i]-i|)

(n)次循环中, 取最小值输出

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
long long p[maxn], has[maxn << 1];
int main() {
    long long n, bigger = 0, smaller = 0, equ = 0, ans1 = 0, ans2 = 0;
    scanf("%lld", &n);
    for (long long i = 1ll; i <= n; i++) {
        scanf("%lld", &p[i]);
        if (p[i] > i) bigger++, has[p[i] - i]++;
        else if (p[i] == i) equ++, has[0]++;
        else smaller++;
        ans1 += abs(p[i] - i);
    }
    long long temp = ans1;
    for (long long last = n - 1ll, delta = 1ll; last >= 1ll; last--, delta++) {
        temp += equ + smaller - bigger;
        smaller += equ;
        bigger -= has[delta];
        if (p[last + 1] >= last + 1ll) has[p[last + 1] - last - 1]--;
        has[p[last + 1] - 1 + delta]++;
        equ = has[delta];
        if (p[last + 1] > 1ll) bigger++;
        smaller = n - equ - bigger;
        temp -= abs(p[last + 1] - n - 1ll) - abs(p[last + 1] - 1ll);
        if (temp < ans1) ans1 = temp, ans2 = delta;
    }
    printf("%lld %lld
", ans1, ans2);
    return 0;
}