【问题描述】

给定一个长度为?的序列?，下标编号为1~?。序列的每个元素都是1~?的

整数。定义序列的代价为

? ?+1 − ? ?

?−1

?=1

你现在可以选择两个数?和?，并将序列?中所有的?改成?。?可以与?相等。

请求出序列最小可能的代价。

【输入格式】

输入第一行包含两个整数?和?。第二行包含?个空格分隔的整数，代表序

列?。

【输出格式】

输出一行，包含一个整数，代表序列最小的代价。

【样例输入 1】

4 6

1 2 3 4 3 2

【样例输出 1】

3

【样例输入 2】

10 5

9 4 3 8 8

【样例输出 1】

6

【样例解释】

样例 1 中，最优策略为将 4 改成 3。样例 2 中，最优策略为将 9 改成 4。

【数据规模和约定】

31。

60%的数据，?,? ≤ 2000。

对于100%的数据，1 ≤ ?,? ≤ 100,000。

 

思路：

　　先把所有的数据都存起来

　　扫一遍把对每个ai[i]有价值的ai[i-1]和ai[i+1]存入动态数组

　　然后从1循环到n

　　如果数组为空则跳过

　　不为空排序

　　取数组中的中位数

　　中位数便是要改成的值

　　然后我们就从1到n中取最优就能ac

 

来，上代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;int n,m,ai[100001],if_Z;long long int ans=0,ans_1=0;char word;vector
          
           ci[100001];inline void read_int(int &now_001){ now_001=0,if_Z=1;word=getchar(); while(word<'0'||word>'9'){ if(word=='-') if_Z=-1;word=getchar();} while(word<='9'&&word>='0'){now_001=now_001*10+(int)(word-'0');word=getchar();} now_001*=if_Z;}int main(){ read_int(n),read_int(m); for(int i=1;i<=m;i++) read_int(ai[i]); for(int i=1;i<=m;i++) { if(i>1&&ai[i]!=ai[i-1]) { ci[ai[i]].push_back(ai[i-1]); ans+=fabs(ai[i]-ai[i-1]); } if(i
           
            >1]; for(int j=0;j