小朋友排队_(归并，逆序对）

原题链接：1215. 小朋友排队 - AcWing题库

题意：小朋友排队，从低到高，每次只能交换相邻的两个人，每换一次，小朋友就会有不高兴值的累加，不高兴程度每次加上其交换的次数，问小朋友不高兴程度的最小值是多少

思路

找逆序对

发现，当一个数左右存在非升序情况（如左边的数比当前大，右边小）这样的数是成对出现的，同时一旦出现就意味着一定要跨越当前数来形成正确的排序。 那找到所有逆序的数就找到了所有要交换的数，再统计一下逆序的数量，等差求和得到最终解。

从代码来看，思路是贪心的：即每次找到逆序就交换，换到不逆序为止，找下一个逆序。

证明：缺乏严格证明，不知道为什么这样最小 只能认为最佳的交换策略可以实现不产生额外的逆序情况，每次交换都可以消除某个逆序。 怎么找？

归并可以对每个区间分到最小，即每次对相邻的两个区间查找，而且区间左右关系确定，可以通过归排选中了哪一个数来判定其左边与右边的逆序情况。

实现

#include <iostream>
#include <algorithm>
 
using namespace std;
 
const int N = 1e5 + 10;
 
typedef long long LL;
typedef pair<LL, LL> PII;
 
PII p[N];
//int cnt[N];
PII t[N];
 
void merge(int l, int r)
{
    if(l >= r)  return;
    
    int mid = l + r >> 1;
    
    merge(l, mid); merge(mid + 1, r);
    
    
    int i = l, j = mid + 1, k = 0;
    while(i <= mid && j <= r)
    {
        if(p[i].first <= p[j].first)
        {
            //i选中了，则j之前所有数都比i小，理应比i大，是逆序
            p[i].second += j - mid - 1;
            t[k ++] = p[i ++];
        }
        else
        {
            //j选中了，则i之后的数比j大，理应比j小
            p[j].second += mid - i + 1;
            t[k ++] = p[j ++];
        }
    }
    
    //如果j先走完了，说明顺序不对
    while(i <= mid)
    {
        p[i].second += j - mid - 1;
        t[k ++] = p[i ++];
    }
    //i先走完说明顺序是对的
    while(j <= r) t[k ++] = p[j ++];
    
    for(int i = l, k = 0; i <= r; i ++, k ++)
        p[i] = t[k];
}
 
 
 
int main()
{
    int n;
    cin >> n;
    
    for(int i = 0; i < n; i ++)
    {
        cin >> p[i].first;
        //p[i].second = i;
    }
    
    merge(0, n-1);
    
    LL ans = 0;
    for(int i = 0; i < n; i ++)
    {
        ans += p[i].second * (p[i].second + 1) / 2;
    }
    
    cout << ans << endl;
    
    return  0;
}