中兴笔试

class Solution
{
public:
    int n = 0;
    void merge(vector<int> &v, int low, int mid, int high)
    {
        int i = 0, index1 = low, index2 = mid + 1;
        vector<int> temp(high - low + 1, 0);
        while (index1 <= mid && index2 <= high)
        {
            if (v[index1] > v[index2])
            {
                n = n + mid - index1 + 1;
                temp[i++] = v[index2++];
            }
            else
                temp[i++] = v[index1++];
        }
        while (index1 < mid + 1)
            temp[i++] = v[index1++];
        while (index2 < high + 1)
            temp[i++] = v[index2++];
        for (int i = 0; i < temp.size(); i++)
            v[low + i] = temp[i];
    }
    void MergeSort(vector<int> &v, int low, int high)
    {
        if (low < high)
        {
            int mid = (low + high) / 2;
            MergeSort(v, low, mid);
            MergeSort(v, mid + 1, high);
            merge(v, low, mid, high);
        }
    }
    int reversePairs(vector<int> &nums)
    {
        MergeSort(nums, 0, nums.size() - 1);
        return n;
    }
};
int main()
{
  int n;
  cin>>n;
  vector<int>v(2*n,0);
  for(int i=0;i<2*n;i++)
  cin>>v[i];
  Solution a;
  cout<<a.reversePairs(v)<<endl;
}

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  while (cin >> n)
  {
    vector<int>result;
    for (int i = 0; i < n; i++)
    {
      int N;
      cin >> N;
      vector<int> v(N, 0);
      for (int index = 0; index < N; index++)
        cin >> v[index];
      int res = INT_MAX;
      if (N == 1 || N == 2)
      cout<<0<<endl;
      else
      {
        int count = 0;
        for (int k0 = -1; k0 <= 1; k0++)
        {
          for (int k1 = -1; k1 <= 1; k1++)
          {
            vector<int> &a = v;
            count = 0;
            a[0] = v[0] + k0;
            a[1] = v[1] + k1;
            int s = a[1] - a[0];
            int index = 2;
            while (index < N && abs(a[index] - a[index - 1] - s) <= 1)
            {
              if (a[index] - a[index - 1] != s)
                count++;
              a[index] = a[index - 1] + s;
              index++;
            }
            if (index == N) //ok
            {
              count = count + abs(k1) + abs(k0);
              res = min(res, count);
            }
          }
        }
        cout<<res<<endl;
      }
    }
  }
}