Inversion

归并排序

#include<bits/stdc++.h>
const int N = 100005;
typedef long long ll;
ll a[N], b[N], cnt;                   //a[N]记录原序列, b[N]记录排序后的序列
void Merge(ll l, ll mid, ll r){
  ll i=l, j = mid+1, t=0;             //定位两序列的索引0
  while(i <= mid && j <= r){          //合并排序
    if(a[i] > a[j]){
      b[t++] = a[j++];
      cnt += mid-i+1;                 //记录逆序对数量
    }
    else b[t++]=a[i++];
  }
  //一个子序列中的数都处理完了，另一个还没有，把剩下的直接复制过来：
  while(i <= mid) b[t++]=a[i++];
  while(j <= r) b[t++]=a[j++];

  for(i=0; i<t; i++) a[l+i] = b[i];  //把排好序的b[]复制回a[]
}
void Mergesort(ll l, ll r){
  if(l<r){
    ll mid = (l+r)/2;                //平分成两个子序列
    Mergesort(l, mid);               //分解
    Mergesort(mid+1, r);
    Merge(l, mid, r);                //合并
  }
}
int main(){
  ll n,k;
  int i;
  while(scanf("%lld%lld", &n, &k) != EOF){     
  cnt = 0;                                     //逆序对数量归零
  for(ll i=0;i<n;i++) scanf("%lld", &a[i]);    //记录序列
    Mergesort(0,n-1);                          //归并排序
    if(cnt <= k) printf("0\n"); 
    else printf("%I64d\n", cnt - k);           //lld%在不同的编译器下使用I64d%
    /*
    for ( i=0 ;i<n ;i++){                      //打印排序后的序列
      printf("%lld",b[i]);                     //打印a或者b都可以
    }
    */
  }
  return 0;
}

笔记：本题要求输出序列里k次修改后的逆序，就是相邻的数字比较大小，并归算法分成三步解决问题：分解，解决，合并