题目链接：

思路：可以想到，要把某一个数字变成他的相邻中的数字的其中一个，这样总和才会减少，于是我们可以把每个数的左右两个相邻的数字存起来，然后我们可以想到，把某个数变成这些相邻的数的中位数总和最小。

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #define REP(i, a, b) for (int i = (a); i < (b); ++i)#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)using namespace std;const int MAX_N = (100000 + 100);int N, M, a[MAX_N];long long sum, ans;vector
         
           neighbor[MAX_N];int main(){ while (cin >> N >> M) { FOR(i, 1, N) neighbor[i].clear(); FOR(i, 1, M) cin >> a[i]; sum = 0; FOR(i, 2, M) if (a[i - 1] != a[i]) { neighbor[a[i - 1]].push_back(a[i]); neighbor[a[i]].push_back(a[i - 1]); sum += abs(a[i - 1] - a[i]); } ans = sum; FOR(i, 1, N) if ((int)neighbor[i].size()) { sort(neighbor[i].begin(), neighbor[i].end()); int _size = (int)neighbor[i].size(); long long tmp = sum; int target = neighbor[i][_size / 2]; REP(j, 0, _size) { tmp = tmp - abs(i - neighbor[i][j]) + abs(target - neighbor[i][j]); } ans = min(ans, tmp); } cout << ans << endl; } return 0;}