题目大意：

现在有一个1~n的全排列，然后定义对于每个数 ai ， disi=|ai−i| ;然后这一串数可以整体向后平移，最后一个跳转到第一个，现在问你如何平移才能使得， ∑ni=1disi 取得最小值。

分析：

dp[i]表示平移第i步之后，有dp[i]个元素的值大于它的位置标号，即在平移第i+1步的时候，有dp[i]个元素的dis值减少了1（不考虑尾部平移到首部的部分）。那么显然可得n-dp[i]个元素的dis值增加了1。然后每次平移对于末尾的元素，只要单独处理一下就可以了。
那么现在如何确定dp[i]呢？对于一个元素a[i]，我O(1)就可以确定他平移多少步的时候就能改变它和下标的大小关系。那么记c[i]表示第i步的时候，数值比位置标号大的个数增加了c[i]个。这样我一个O(n)下去，就知道了每次移动比上一次改变了多少。再一个O(n)就知道了所有的dp值，再一个O(n)就得到了所有dis值的和的最小值和对应的移动步数。

小记：

这个边界太容易出错了，因为多加了一个1，从昨天查到现在，最后还是自己生成数据对排+手动模拟才找到的问题。。。。后面另附测试数据生成器以及对排差错程序。

代码：

#include<bits/stdc++.h>
using namespace std;
#define maxn 1000500

int dis[maxn],dp[maxn],a[maxn],n;
int c_inc[maxn];//移动第i步的时候，有多少个从值大于标号变为值小于等于标号
int c_red[maxn];//移动第i步的时候，有多少个从值小于等于标号变为值大于标号
long long int ans;



void init()
{
    memset(c_inc,0,sizeof(c_inc));
    memset(c_red,0,sizeof(c_red));
    memset(dp,0,sizeof(dp));
}

void add(int pos,int val)
{
    if(val>pos)
    {
        dp[0]++;
        c_red[n-pos+1]++;
        c_inc[val-pos]++;
    }
    else
    {
        if(val==1)return;
        c_red[n-pos+1]++;
        c_inc[n-pos+val]++;
    }
}

int main()
{
    scanf("%d",&n);
    init();
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        add(i,a[i]);
        ans+=(long long int)abs(a[i]-i);
    }
    int best_t=0;
    long long int best_ans=ans;
    //cout<<ans<<" "<<0<<endl;
    for(int i=1;i<n;i++)
    {
        dp[i]=dp[i-1]+c_red[i]-c_inc[i];
        ans+=(n-2*dp[i-1]);
        ans--;
        ans+=(2*a[n-i+1]-n-1);
        //cout<<ans<<" "<<i<<" "<<dp[i]<<endl;
        if(ans<best_ans)
        {
            best_ans=ans;
            best_t=i;
        }
    }
    printf("%lld %d",best_ans,best_t);
    //cout<<best_ans<<" "<<best_t;
}

数据生成代码：

#include<bits/stdc++.h>
#define maxn 10000
using namespace std;
bool appear[maxn]={0};
int a[maxn];
int main()
{
    int n,m;
    srand( (unsigned)time( NULL ) );
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        while(1)
        {
            int t=rand()%n;
            t++;
            if(appear[t]==0)
            {
                appear[t]=1;
                a[i]=t;
                break;
            }
        }
        //scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++)
    {
        printf("%d ",a[i]);
    }
    //-----------------------------------暴力求解答案-------------------------
    int ans,best_t=-1;
    for(int i=0;i<n;i++)
    {
        int now=0;
        for(int j=1;j<=n;j++)
        {
            now+=(abs(a[j]-((i+j-1)%n+1)));
        }
        //cout<<now<<" "<<i<<endl;
        if(now<ans||best_t==-1)
        {
            ans=now;
            best_t=i;
        }
    }
    cout<<endl<<ans<<" "<<best_t;
    //------------------------------------------------------------------------------
}

对排查错程序：

#include<bits/stdc++.h>
using namespace std;
#define maxn 1000500

int dis[maxn],dp[maxn],a[maxn],n;
int c_inc[maxn];//移动第i步的时候，有多少个从值大于标号变为值小于等于标号
int c_red[maxn];//移动第i步的时候，有多少个从值小于等于标号变为值大于标号
long long int ans;
bool appear[maxn]={0};


void init()
{
    memset(c_inc,0,sizeof(c_inc));
    memset(c_red,0,sizeof(c_red));
    memset(dp,0,sizeof(dp));
    memset(appear,0,sizeof(appear));
    ans=0;
}

void add(int pos,int val)
{
    if(val>pos)
    {
        dp[0]++;
        c_red[n-pos+1]++;
        c_inc[val-pos]++;
    }
    else
    {
        if(val==1)return;
        c_red[n-pos+1]++;
        c_inc[n-pos+val]++;
    }
}

void output()
{
    for(int i=1;i<=n;i++)
    {
        cout<<a[i]<<" ";
    }
}

bool compare(long long int x,int y)
{
    long long int ans;
    int best_t=-1;
    for(int i=0;i<n;i++)
    {
        long long int now=0;
        for(int j=1;j<=n;j++)
        {
            now+=(abs(a[j]-((i+j-1)%n+1)));
        }
        if(now<ans||best_t==-1)
        {
            ans=now;
            best_t=i;
        }
    }
    if(ans!=x||best_t!=y)
    {
        output();
        printf("\n\n%lld %d \n%lld %d",x,y,ans,best_t);
        return 1;
    }
    return 0;
}

int main()
{
    int flag=0;
    while(flag!=1)
    {
        n=rand()%8+1;
        init();
        for(int i=1;i<=n;i++)
        {
            while(1)
            {
                int t=rand()%n;
                t++;
                if(appear[t]==0)
                {
                    appear[t]=1;
                    a[i]=t;
                    add(i,a[i]);
                    ans+=(long long int)abs(a[i]-i);
                    break;
                }
            }
        }
        int best_t=0;
        long long int best_ans=ans;
        //cout<<ans<<" "<<0<<endl;
        for(int i=1;i<n;i++)
        {
            dp[i]=dp[i-1]+c_red[i]-c_inc[i];
            ans+=(n-2*dp[i-1]);
            ans--;
            ans+=(2*a[n-i+1]-n-1);
            //cout<<ans<<" "<<i<<endl;
            if(ans<best_ans)
            {
                best_ans=ans;
                best_t=i;
            }
        }
        flag=compare(best_ans,best_t);
        //printf("%lld %d",best_ans,best_t);

    }

    //cout<<best_ans<<" "<<best_t;
}

总结：

回头看一下，首先如果枚举每一种可能的移动方式，每次在求一次dis值的和，那么时间复杂度是 O(n2) ，那么我究竟少计算了什么，才使得时间复杂度降为 O(n) 了呢？

首先，我们可以发现，每一次平移，对于一个数，它的dis值要么就是+1要么就是-1。
ps：注意这里我是把一个数值作为研究对象而不是它的位置，也就是说，对于这个数，它的位置可以不断改变，同时它的dis值也在对应改变，但是，只要它的值不变，那它就还是原来的数。

现在，我研究的，就是这样的数。那就可以发现，他在移动的过程中，他的值和它的位置标号的大小关系只会转变两次，而且这两次我一个O(1)就确定了。
那么我就想，能不能在O(1)的时间内知道每次移动一步的时候，和移动之前相比，dis和的变化量。然后我发现，知道知道移动前的“状态”就可以了。这个“状态”就是值，当前有多少数是值大于标号，有多少数是值小于等于标号。
那么又要怎样知道每一个状态呢？还是想能不能用每前一个状态来得到当前状态。我只要知道这一步一动有多少数的值和它的位置标号大小关系改变了，就可以从上一个状态得到当前状态了。而之前也说了，只要遍历一次原数组，O(n)时间就能确实每一步会有多少个数大小关系改变。

总的来说，就是首先一次遍历初始化（这种思想挺常见的，但是我不知道怎么称呼它。就是对于每一个数，单独研究它对整体的影响。这样依次研究每一个数。），然后就是两次线性递推动规。