蓝桥杯学习总结（二七）

3.习题

这几道习题都有一定难度。

3.1 acwing.1215. 小朋友排队

第五届蓝桥杯省赛C++B/C组

n 个小朋友站成一排。
现在要把他们按身高从低到高的顺序排列，但是每次只能交换位置相邻的两个小朋友。
每个小朋友都有一个不高兴的程度。
开始的时候，所有小朋友的不高兴程度都是 0。
如果某个小朋友第一次被要求交换，则他的不高兴程度增加 1，如果第二次要求他交换，则他的不高兴程度增加 2（即不高兴程度为 3），依次类推。当要求某个小朋友第 k 次交换时，他的不高兴程度增加 k。
请问，要让所有小朋友按从低到高排队，他们的不高兴程度之和最小是多少。
如果有两个小朋友身高一样，则他们谁站在谁前面是没有关系的。

输入格式
输入的第一行包含一个整数 n，表示小朋友的个数。
第二行包含 n 个整数 H1,H2,…,Hn，分别表示每个小朋友的身高。

输出格式
输出一行，包含一个整数，表示小朋友的不高兴程度和的最小值。

数据范围
1≤n≤100000,
0≤Hi≤1000000
输入样例：
3
3 2 1
输出样例：
9
样例解释
首先交换身高为3和2的小朋友，再交换身高为3和1的小朋友，再交换身高为2和1的小朋友，每个小朋友的不高兴程度都是3，总和为9。

思路：

看这题目就是一道贪心问题，可以用冒泡（归并）排序来处理。

序列中逆序对的数量就是至少要交换的次数，使逆序数对变得有序。

证明：在冒泡排序中，每交换一次相邻的两个数，必然使逆序对数量-1，因为这两个数之外的部分相对位置没

有改变，逆序对不受影响。所以有k个逆序对，至少需要交换k次。在冒泡排序中，有k个逆序对就需要k次交

换。所以贪心策略是k个逆序对进行k次交换。

可以证明，每个小朋友需要交换的次数是前面比它大的数和后面比它小的数，因为如果前面有比它大的数，那

么它必定和前面的交换一次，使得前面大的数排到后面，同理可以知道比它小的数一定要和它交换到前面

那么我们求每个小朋友a[i]前后比它大/小的数（也即a[i]的逆序对总数）就有三种方法，冒泡排序、归并排序

与树状数组。

对于序列中每个数的逆序对数量：前面比它大的数k1和后面比它小的数k2，他的不高兴度就是1+2+3+...+(k1+k2)。int最大值约为2*10^9，会爆int。

题解1：暴力法。时间复杂度：O(n^2)，目前TLE。

参考题解：https://www.acwing.com/solution/content/7296/。

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n;
long long ans;
long long a[N],num[N];

long long summary(long long x){
    int k;
    k=(1+x)*x/2;
    return k;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }

    for(int i=1;i<=n;i++){
        long long res=0;
        for(int j=1;j<i;j++){
            if(a[j]>a[i]){
                res++;
            }
        }
        for(int j=i+1;j<=n;j++){
            if(a[j]<a[i]){
                res++;
            }
        }
        res=summary(res);
        num[i]=res;
    }
    for(int i=1;i<=n;i++){
        ans+=num[i];
    }
    cout<<ans<<endl;
    return 0;
}

题解2：树状数组，维护了区间中小朋友身高出现的次数。时间复杂度：O(n*logn)。

参考代码：y总，参考思路：https://www.acwing.com/solution/content/7296/。

每次读入一个数就先把它放到树状数组中去，但这个树状数组保存的并不是这个数，而是这个数出现的次数。

#include <cstdio>
#include <algorithm>
#include <iostream>
typedef long long LL;
using namespace std;

const int N = 1000010;// 树状数组以身高为下标
int h[N],tr[N],sum[N];
int n;
int lowbit(int x){
    return x & -x;
}

void add(int x,int v){
    for (int i = x;i <= N;i += lowbit(i)) tr[i] += v;
}

int query(int x){
    int res = 0;
    for (int i = x;i;i -= lowbit(i)) res += tr[i];
    return res;
}

int main(){
    scanf("%d",&n);
    for (int i = 1;i <= n;i ++) scanf("%d",&h[i]),h[i]++;// 注意身高可能为0，但是树状数组下标从1开始

    // 计算每个数前面有多少个数比它大，正向枚举，求的就是前面数中多少个数比它大
    for (int i = 1;i <= n;i ++){
        // 等价于sumn[i] = i - query(h[i])，i是前面出现数的个数
        sum[i] = query(N-1) - query(h[i]);
        add(h[i],1);
    }

    // 计算每个数后面有多少个数比它小，这里一定要逆序枚举
    // 记得清空数组
    memset(tr,0,sizeof tr);
    for (int i = n;i;i --){
        sum[i] += query(h[i]-1);
        add(h[i],1);
    }
    // 答案存LL
    LL res = 0;
    for (int i = 1;i <= n;i++){
        res += (LL)sum[i]*(sum[i]+1)/2;
    }
    printf("%lld\n",res);
    return 0;
}

题解3：归并排序。时间复杂度：O(n*logn)。

参考题解：https://www.acwing.com/solution/content/42097/。

类似题目：acwing.788. 逆序对的数量。

我们把所有小朋友的身高按读入的顺序进行归并排序，分别统计每个小朋友的逆序对。

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y second
const int  N = 100010;

int n;
LL h[N];
PII temp[N];
PII w[N];

void merge_sort(int l,int r){
    if (l >= r) return;
    int mid = l + r >> 1;
    merge_sort(l,mid),merge_sort(mid+1,r);
    
    int i = l,j = mid+1,k = 0;
    while (i <= mid && j <= r){
        if (w[i].x <= w[j].x){// 计算i后面比它小的数的个数
            h[w[i].y] += j - mid -1;// 相对于i来说，j 前面的数都比它小
            temp[k++] = w[i++];
        }
        else{// 计算j前面比它大的数的个数
            h[w[j].y] += mid - i +1;// 相对于j来说，i 后面的数都比它大
            temp[k++] = w[j++]; 
        } 
    }
    
    while (i <= mid){// 计算i后面比它小的数的个数
        h[w[i].y] += r - mid;// 相对于i来说，mid+1到r所有的数都比它小
        temp[k++] = w[i++];
    }
    while (j <= r){
        temp[k++] = w[j++];// 相对于j来说，不存在逆序对了
    }
    // 物归原主
    for (int i = l,j = 0;i <= r;i++,j++) w[i] = temp[j];
}
int main(){
    scanf("%d",&n);// w[i]第一维是身高，第二维是下标，读入顺序
    for (int i = 0;i < n;i++) scanf("%d",&w[i].x),w[i].x++,w[i].y = i;
    merge_sort(0,n-1);
    
    LL res = 0;
    for (int i = 0;i < n;i++){
        res += (LL)h[i]*(h[i]+1)/2;
    }
    printf("%lld\n",res);
    return 0;
}