题目描述
小蓝老师教的编程课有 N 名学生,编号依次是 1…N。第 i 号学生这学期刷题的数量是 Ai。
对于每一名学生,请你计算他至少还要再刷多少道题,才能使得全班刷题比他多的学生数不超过刷题比他少的学生数。
样例
5
12 10 15 20 6
分类讨论
看到题解里很多说是用二分的,所以想说一说这题其实不用二分,就是一个单纯的分类讨论。
因为二分之前我们已经对数组进行排序了,这个时候我们就可以直接通过找索引为n / 2的值为中位数
解释:这里不论偶数还是奇数都可以这样,因为对于奇数,一定是最中间的数;对于偶数,则为两个中间数的后一个,偶数这样可以直接在后面讨论的时候,改动后保证less >= more——因为小于等于这个数的数量一定是大于等于这个数的数量的,所以满足后续讨论。
那么直接进行讨论:
-
对于大于mid的数而言,因为小于等于mid本身的数就至少有n / 2个,所以大于mid的数就自然一定满足条件。答案为0
-
对于等于mid的数而言,同理,小于等于mid本身的数就至少有n / 2个。那么就分为2种情况:
## less >= more:这时不用加就满足条件。答案为0
## less < more:这时就必须增加less的数,因此直接在此基础上加1就能去掉小于等于mid的等号条件,变成小于这个数的数至少有n / 2个。答案为1。 - 对于小于mid的数而言,其实也是类似的:
## less > more:为什么这里不取等于,是因为我们肯定要让这个数变为中位数后,再进行改动,如果这里没有等于,变成中位数后,我们只会少一个数为less,因此满足less >= more。答案为mid - task[i]
## less <= more:那这里肯定在变为中位数后,一定要让less的值变多,因此在中位数上加1,逻辑和之前类似。答案为mid - task[i] + 1
时间复杂度
$O(nlogn)$
参考文献
Java 代码
import java.io.*;
import java.util.*;
public class Main{
static BufferedReader rd;
static BufferedWriter wr;
final static int N = 100010;
static int n;
static int[] tasks = new int[N];
static int[] temp = new int[N];
public static void main(String[] args) throws IOException{
rd = new BufferedReader(new InputStreamReader(System.in));
wr = new BufferedWriter(new OutputStreamWriter(System.out));
int less = 0;
int more = 0;
n = Integer.parseInt(rd.readLine().trim());
String[] t1 = rd.readLine().split(" ");
for(int i = 0; i < n; i++){
tasks[i] = Integer.parseInt(t1[i]);
temp[i] = Integer.parseInt(t1[i]);
}
Arrays.sort(tasks,0,n);
int mid = tasks[n / 2];
for(int i = 0; i < n; i++){
if(tasks[i] < mid){
less++;
}else if(tasks[i] > mid){
more++;
}
}
for(int i = 0; i < n; i++){
if(temp[i] > mid){
wr.write(0 + " ");
}else if(temp[i] == mid){
if(less >= more){
wr.write(0 + " ");
}else{
wr.write(1 + " ");
}
}else{
if(less > more){
wr.write(mid - temp[i] + " ");
}else{
wr.write(mid - temp[i] + 1 + " ");
}
}
}
wr.flush();
wr.close();
rd.close();
}
}