题意

• 给定1~n的排列和中位数b，构造子列使得中位数是b

思路

• 比b大的记为1，小的记为-1，对b左右做后缀和和前缀和，统计每种答案个数，将前后和中互为相反数的相乘

AC代码

#include<bits/stdc++.h>
using namespace std;
#define base 100000
int a[101010];
int l[101010],r[101010],ctl[303030],ctr[303030];//记录左半边和右半边出现频率，反着记方便相乘
int main(){
    int n,b,pos,ans=0;
    scanf("%d%d",&n,&b);
    for(int i=0;i<n;i++){
        int tp;
        scanf("%d",&tp);
        if(tp>b) a[i]=1;
        else if(tp<b) a[i]=-1;
        else {a[i]=0;pos=i;}
//         printf("%d ",a[i]);
    }
    for(int i=pos;i>=0;i--){
        l[i]=l[i+1]+a[i];
        ctl[base+l[i]]++;
    }
    for(int i=pos;i<n;i++){
        r[i]=r[i-1]+a[i];
        ctr[base-r[i]]++;
    }
    for(int i=0;i<303030;i++){
        ans+=ctr[i]*ctl[i];
    }
    printf("%d",ans);
    return 0;
    
}

补充：中位数和带权中位数

• 对于数轴上若干点，将它们移动到同一个点，欲使移动距离最小，应将他们移到中位数所在的位置

• 证明如下：对于移动到每一个位置，可知总距离为:

• 不妨认为已经将全部点移动到权值中位数位置，此时，左右权值相同设为，无论向左或向右移动，均有的权值要多移动而的权值要少移动，故该点为最优解

• tips：对于一下其它形式的问题，可通过将所有点先移到最左，变形上述式子，求出每一个位置的总距离，最后 遍历一遍序列即可得到最小值