（第一次做题解，可能讲的不是很详细）

看题意，给定数组长度n和数组a，求每次删掉第i个元素后，数组的中位数。

如果按纯暴力的方法，如：每次重建一个数组再找到当前数组的中位数，这样肯定会超时的（毕竟数据是2≤ ai ≤10^5），所以，必须要找规律。

以下是思路：

首先将数组重新排列，这样，如果n是奇数则原数组的中位数是a[n/2+1]，如果n是偶数则原数组的中位数是(a[n/2]+a[n/2+1])/2。

这有什么用呢？以n=4，ai=1~n的数组a为例：

当ai==1时： alt

当ai==4时：

alt

很显然，当当前值的下标小于n/2时，中位数往后移一位，即a[n/2]-->a[n/2+1];当大于n/2时往后移一位，即a[n/2]-->a[n/2+1]；

奇数时同理，但要特判当下标==n/2时的情况。

详细代码如下：

	sort(a,a+n,cmp);//对原数组进行排序;
    if (n%2==1)//当n为奇数时，所求数组为n-1，即实际数组长度为偶数;
    {
        for (int i=0;i<n/2;i++)b[i]]=a[n/2]+a[n/2+1];//当i<n/2时，中位数为n/2和n/2+1上的值的和除2;
        b[n/2]=a[n/2-1]+a[n/2+1];//当i=n/2时，中位数为n/2-1和n/2+1上的值的和除2;
        for (int i=n/2+1;i<n;i++)b[i]=a[n/2-1]+a[n/2];//当i>n/2时，中位数为n/2-1和n/2上的值的和除2;
    }
    else//当n为偶数时，实际长度为奇数;
    {
        for (int i=0;i<n/2;i++)b[i]=a[n/2]*2;//当i<n/2时，中位数为n/2;
        for (int i=n/2;i<n;i++)b[i]=a[n/2-1]*2;//当i<n/2时，中位数为n/2+1;
    }

规律找到了，接下来就是怎么输出了，毕竟原数组已经被重新排列了，如果直接输出，那就会按从小到大的顺序输出ai的中位数了，这样肯定是不行的，所以，我们需要另一个数组b来帮我们存储i时的中位数，那要怎么存呢。 详情如下:

首先利用结构体，记录a原先的数值num和下标id；

    {
        cin >>a[i].num;//记录ai的数值;
        a[i].id=i;//记录ai的下标;
    }

再通过结构体的数值num和下标id相互绑定，因此在数值num排序时，下标id也跟着排列，但下标id的数值可没变啊，所以b[a[i].id]记录的是原来a[i].num所在的位置； 代码如下：

    if (n%2==1)//当n为奇数时，所求数组为n-1，即实际数组长度为偶数;
    {
        for (int i=0;i<n/2;i++)b[a[i].id]=a[n/2].num+a[n/2+1].num;//当i<n/2时，中位数为n/2和n/2+1上的值的和除2;
        b[a[n/2].id]=a[n/2-1].num+a[n/2+1].num;//当i=n/2时，中位数为n/2-1和n/2+1上的值的和除2;
        for (int i=n/2+1;i<n;i++)b[a[i].id]=a[n/2-1].num+a[n/2].num;//当i>n/2时，中位数为n/2-1和n/2上的值的和除2;
    }
    else//当n为偶数时，实际长度为奇数;
    {
        for (int i=0;i<n/2;i++)b[a[i].id]=a[n/2].num*2;//当i<n/2时，中位数为n/2;
        for (int i=n/2;i<n;i++)b[a[i].id]=a[n/2-1].num*2;//当i<n/2时，中位数为n/2+1;

为了防止还是不太会写， 以下是ac代码：

#include <bits/stdc++.h>
using namespace std;

const int N=1e6+10;
//简单的结构体数组,其实id，num可以写到一行，这里是方便注释;例：int id,num;
struct Index{
    int id;//ai的下标，使数组b能够以ai原先的顺序记录ai时的中位数，同时使数值不爆数组上限；
    int num;//ai的数值.
}a[N];
int b[N];//记录ai时的中位数。

bool cmp(Index a,Index b){
    return a.num<b.num;//将数值从小到大排，这个应该会吧,(-_-|||)。
}
//中位数统一处理，节省代码长度;
void f(int x){
    double w=1.0*x/2;//计算中位数的值,x*0.1是将数值类型由实数转化为浮点型；
    printf("%.1f\n",w);//输出保留一位小数的值;
}

int main() {
    int n;
    cin >>n;//数组长度
    for (int i=0;i<n;i++)
    {
        cin >>a[i].num;//记录ai的数值;
        a[i].id=i;//记录ai的下标;
    }
    sort(a,a+n,cmp);//对原数组进行排序;
    if (n%2==1)//当n为奇数时，所求数组为n-1，即实际数组长度为偶数;
    {
        for (int i=0;i<n/2;i++)b[a[i].id]=a[n/2].num+a[n/2+1].num;//当i<n/2时，中位数为n/2和n/2+1上的值的和除2;
        b[a[n/2].id]=a[n/2-1].num+a[n/2+1].num;//当i=n/2时，中位数为n/2-1和n/2+1上的值的和除2;
        for (int i=n/2+1;i<n;i++)b[a[i].id]=a[n/2-1].num+a[n/2].num;//当i>n/2时，中位数为n/2-1和n/2上的值的和除2;
    }
    else//当n为偶数时，实际长度为奇数;
    {
        for (int i=0;i<n/2;i++)b[a[i].id]=a[n/2].num*2;//当i<n/2时，中位数为n/2;
        for (int i=n/2;i<n;i++)b[a[i].id]=a[n/2-1].num*2;//当i<n/2时，中位数为n/2+1;
    }
    for (int i=0;i<n;i++)f(b[i]);//遍历记录的bi输出计算后的中位数
    return 0;
}

ok,以上就是整篇文章，See you next solution