codeforces 820 D. Mister B and PR Shifts（思维）

题目链接：http://codeforces.com/contest/820/problem/D

题意：求.有一种操作

• k = 0: shift p1, p2, ... pn,
• k = 1: shift pn, p1, ... pn - 1,
• ...,
• k = n - 1: shift p2, p3, ... pn, p1.  
  这样的操作，问sum值最小是多少需要操作几次

题解：这题其实只要模拟一下操作就行了复杂度为O(n)具体看一下代码。

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

const int M = 1e6 + 10;

typedef long long ll;

int a[M] , pre[M];//pre[i]可以理解为再向前移动i位后a[i]-i<=0。

int main() {

    int n;

    scanf("%d" , &n);

    for(int i = 1 ; i <= n ; i++) scanf("%d" , &a[i]);

    ll sum = 0 , Min;

    int ans = 0;

    memset(pre , 0 , sizeof(pre));

    for(int i = 1 ; i <= n ; i++) {

        sum += abs(a[i] - i);

        if(a[i] - i <= 0) pre[0]++;

        else pre[a[i] - i]++;

    }

    Min = sum;

    int cnt = pre[0];//cnt表示上个状态有多少a[i]-i<=0,sum就可以加上cnt，因为前移后结果肯定是变大的。

    for(int i = 1 ; i < n ; i++) {

        int pos = n - i + 1;

        if(a[pos] - n <= 0) cnt--;//由于pos位置是要移动到第一位的所以要判断一下，因为后面pos位置和首位会另外处理

        if(a[pos] - pos <= 0) pre[0]--;//更新状态

        else pre[a[pos] - pos]--;

        pre[min(a[pos] + i - 1 , M - 10)]++;//由于i表示已经总体向后移动了i位而且第i个数已经移到首位。所以pos位移动到第一位还要再加上i

        sum += cnt;

        sum -= (n - cnt - 1);//那些原来a[i]-i>0前移之后贡献肯定减少。所以这里减去,再处理掉首位。首尾额外处理

        sum -= abs(a[pos] - n);

        sum += abs(a[pos] - 1);

        cnt += pre[i];

        if(sum < Min) {

            ans = i;

            Min = sum;

        }

    }

    printf("%lld %d\n" , Min , ans);

    return 0;

}