历届试题 小朋友排队  
时间限制:1.0s   内存限制:256.0MB
 
问题描述
  n 个小朋友站成一排。现在要把他们按身高从低到高的顺序排列,但是每次只能交换位置相邻的两个小朋友。

  每个小朋友都有一个不高兴的程度。开始的时候,所有小朋友的不高兴程度都是0。

  如果某个小朋友第一次被要求交换,则他的不高兴程度增加1,如果第二次要求他交换,则他的不高兴程度增加2(即不高兴程度为3),依次类推。当要求某个小朋友第k次交换时,他的不高兴程度增加k。

  请问,要让所有小朋友按从低到高排队,他们的不高兴程度之和最小是多少。

  如果有两个小朋友身高一样,则他们谁站在谁前面是没有关系的。
输入格式
  输入的第一行包含一个整数n,表示小朋友的个数。
  第二行包含 n 个整数 H1 H2 … Hn,分别表示每个小朋友的身高。
输出格式
  输出一行,包含一个整数,表示小朋友的不高兴程度和的最小值。
样例输入
3
3 2 1
样例输出
9
样例说明
  首先交换身高为3和2的小朋友,再交换身高为3和1的小朋友,再交换身高为2和1的小朋友,每个小朋友的不高兴程度都是3,总和为9。
数据规模和约定
  对于10%的数据, 1<=n<=10;
  对于30%的数据, 1<=n<=1000;
  对于50%的数据, 1<=n<=10000;
  对于100%的数据,1<=n<=100000,0<=Hi<=1000000。
 
思路:
 
首先我们来分析一下这组数据。
4
1 9 5 2
 
那么对于第1的元素,它左边没有比它大的,右边没有比它小的,所以它不需要移动
第二个元素9,因为右边有一个5比它小,所以9需要移动1一次。
第三个元素5,左边有一个数9比它大,右边有一个数2比它小,所以它需要移动 两次。
而最后一个元素2,因为左边有两个元素比它大,所以它需要移动两次。
 
那么我们可以观察出规律。
对于第i个数,当移动次数最优的时候,它需要移动的次数就等于左边比它大的数的个数,和右边比它小的数的个数的总和。
 
那么我们知道这个规律后,我们该如何解决这个问题呢?
上面提到的规律中涉及到逆序对的问题,那么在n<=1e5的数据范围条件下,n*n来求每一个元素的逆序对显然会TLE的。
那么我们就要用到树状数组求依序对。
如果不知道树状数组这个数据结构,可以自行百度学习。
这里会用到最简单的树状数组的模板。
 
我们知道,对于树状数组,query(  a[i] ) 等于 1~a[i]的前缀和
我们从左到右遍历数组的时候,对于第i个元素,当前已经加入了i个元素(包括自己)。那么调用query函数求1~a[i]的前缀和后,
 i - a[i]  就等于在前面i-1个中,有多少个数比a[i] 大,因为如果比a[i]小,就会被算在query( a[i] ) 中。
而前面的数比后面的数大就是我们要找的逆序对,即左边比它大的数的个数。
那么右边同理:
我们只需要从右向左扫求每一个数a[i] 的前缀和即代表这第i个数后面有多少个数比它小。
然后对应求一个每一个元素的移动次数的愤怒值,加在一起就是答案了。
注意树状数组不能对0位置加数,
而输入数据的身高有0,所以我们对数据的每一个身高都加1,这样并不会影响结果。(因为考虑的都是相对大小)
 
细节见代码:(满分)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#define sz(a) int(a.size())
#define all(a) a.begin(), a.end()
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define gg(x) getInt(&x)
#define db(x) cout<<"==  "<<x<<"  =="<<endl;
using namespace std;
typedef long long ll;
inline void getInt(int* p);
const int maxn=1000010;
const int inf=0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
int n;
ll a[maxn];
ll b[maxn];
ll tree[maxn];
#define lowbit(x) (x)&(-x)
void add(int i)
{
    while(i<=maxn)
    {
        tree[i]+=1;
        i+=lowbit(i);
    }
}
ll query(int i)
{
    ll res=0;
    while(i>0)
    {
        res+=tree[i];
        i-=lowbit(i);

    }
    return res;
}
ll num[maxn];
int main()
{
    gbtb;
    cin>>n;
    repd(i,1,n)
    {
        cin>>a[i];
        a[i]++;
    }
    ll tot=0ll;
    repd(i,1,n)
    {
        add(a[i]);
        tot=i-query(a[i]);// 统计当前序列中大于a的元素的个数
        num[i]+=tot;
    }
    MS0(tree);
    for(int i=n;i>=1;i--)
    {
        add(a[i]);
        tot=query(a[i]-1);
        num[i]+=tot;
    }
    ll ans=0ll;
    repd(i,1,n)
       {
//            cout<<i<<" "<<num[i]<<endl;
           ans+=(num[i]*(1ll+num[i]))/2ll;
       }
       cout<<ans<<endl;

    return 0;
}

inline void getInt(int* p) {
    char ch;
    do {
        ch = getchar();
    } while (ch == ' ' || ch == '\n');
    if (ch == '-') {
        *p = -(getchar() - '0');
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 - ch + '0';
        }
    }
    else {
        *p = ch - '0';
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 + ch - '0';
        }
    }
}