自动搬运

查看原文

来自洛谷，原作者为

	pigstd Hello, the cruel world.

搬运于2025-08-24 21:54:59，当前版本为作者最后更新于2020-09-15 20:08:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先把所有学生按照成绩排序，排序后，设$f1_i$表示$1 - i$之中，奖学金前$\frac {c-1} 2$小的奖学金之和，$f2_i$表示$i - n$之中，奖学金前$\frac {c-1} 2$小的奖学金之和

我们枚举每一个可能作为中位数的学生，那么，如果一个学生$i$能够作为中位数，那么就应该满足：$b_i + f1_{i - 1} + f2_{i+1} \le f$

那么现在的问题就是怎么求出$f1_i$和$f2_i$

那么显然我们可以推出：$f1_i=f1_{i-1}+\min(0,b_i-min1 _{i-1,\frac {c-1} 2})$，$f2_i=f2_{i+1}+\min(0,b_i-min2 _{i+1,\frac {c-1} 2})$，其中$min1_{k,j}$表示当$i = 1$到$k$中所有$b_{i}$中第$j$小的数，$min1_{k,j}$表示当$i = k$到$n$中所有$b_{i}$中第$j$小的数

那么怎么求出$min1$和$min2$呢？可以写两个权值线段树，也可以直接写一个主席树维护

代码：code