代码拉取完成，页面将自动刷新
蓝桥杯题库 题目链接。
思维，前缀和，省赛，2022
因为是真题官方题解比较详细，这里直接使用官方题解
暴力枚举每个学生的成绩，当满足比该学生成绩小的个数不少于比该学生成绩好的个数时，输出答案
时间复杂度为 $O(n\times max(a_i))$。
首先我们观察题目，题目中我们要求实现成绩比自己小的人数不少于成绩比自己大的人数的最小刷题数，于是我们可以用数组记录每个成绩出现的次数 ，然后维护成绩的前缀和，并遍历遍历数组，如果当前成绩比自己小的人数不少于成绩比自己大的人数 ，我们把大于等于该成绩的学生定义为合法学生，即不用进行任何操作就可以满足要求。
反之，我们要分析不合法学生变成合法学生的最小刷题数，首先我们要找到一个当前成绩比自己小的人数多于比成绩比自己大的合法学生的最小成绩，定义为通过刷题可以成为合法学生的所需的最小成绩。
然后我们对每一个不合法学生，我们用上述所说的最小成绩减去当前成绩，便是不合法学生的最小刷题数，若为合法学生，最小刷题数为 0。
时间复杂度为 $O(n)$
import java.util.Scanner;
public class Main {
static final int N = 100000 ;
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int a[] = new int[n + 1] ;
int cnt[] = new int[N + 1] ;
int maxn = 0 ;
for(int i = 1 ; i <= n ; i ++) {
a[i] = scan.nextInt();
cnt[a[i]] ++ ;
maxn = Math.max(maxn , a[i]) ;
}
for(int i = 1 ; i <= maxn ; i ++) {
cnt[i] += cnt[i - 1] ;
}
int pos = -1 ;
int pos1 = -1 ;
for(int i = 1 ; i <= maxn ; i ++) {
if(cnt[i - 1] >= n - cnt[i]) {
if(pos1 == -1) pos1 = i ;
}
if(cnt[i - 1] - 1 >= n - cnt[i]) {
if(pos == -1) {
pos = i ;
break ;
}
}
}
if(pos == -1) {
for(int i = 1 ; i <= n ; i ++) {
System.out.print("0 ") ;
}
}else {
for(int i = 1 ; i <= n ; i ++) {
if(a[i] >= pos1) System.out.print("0 ");
else System.out.print(pos - a[i] + " ");
}
}
scan.close();
}
}
此处可能存在不合适展示的内容，页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容，可点击提交进行申诉，我们将尽快为您处理。
马建仓 AI 助手
