Ryouko's Memory Note

题目意思：一个书有 n 页，每页的编号依次从 1 到 n 编排。如果从页 x 翻到页 y，那么|x-y|页都需要翻到（联系生活实际就很容易理解的了）。接着有m pieces 的 information，第 i piece 的information 在第 a[i] 页。为了减少翻页的页数，允许把某一页的信息，完全搬到某一页上，这个操作只可以执行一次。问应该把哪一页的信息搬到某一页上，从而使得翻页次数最少。

使用vector记录一个数两边的数字，然后把这些数字排序，选中间的那个当做修改后的值.

#include<stdio.h>

#include<algorithm>

#include<vector>

using namespace std;

const int MAX = ;

int a[MAX];

vector<int>ne[MAX];//相邻页

int fabs(int x)

{

    if(x<)x=-x;

    return x;

}

int main()

{

    int n,m;

    int i,j;

    int tmp1,tmp2;

    long long sum1,sum2,maxdis;

    long long ans;

    while(scanf("%d %d",&n,&m)!=EOF)

    {

        for(i=;i<m;i++)

            scanf("%d",&a[i]);

        for(i=;i<m-;i++)//statistics

        {

            if(a[i]!=a[i+])

            {

                ne[a[i]].push_back(a[i+]);

                ne[a[i+]].push_back(a[i]);

            }

        }

        maxdis = ;

        ans=;

        for(i=;i<=n;i++)//sort

        {

            if(!ne[i].empty())

            {

                sort(ne[i].begin(),ne[i].end());

                tmp2 = ne[i].size()/;

                tmp1 = ne[i][tmp2];

                sum1=;

                sum2=;

                for(j=;j<ne[i].size();j++)

                {

                    sum1+=fabs(ne[i][j]-tmp1);

                    sum2+=fabs(ne[i][j]-i);

                }

                maxdis = max(maxdis,sum2-sum1);

                ans+=sum2;// total turn page former

            }

        }

        printf("%I64d\n",ans/-maxdis);

        for(i=;i<=n;i++)

            ne[i].clear();

    }

    return ;

}