题解 P3963 【[TJOI2013] 奖学金】

pigstd · 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