1.最少刷题数

1.题目描述

小蓝老师教的编程课有 $N$ 名学生, 编号依次是 $1\dots N$ 。第 $i$ 号学生这学期 刷题的数量是 Ai A_{i}Ai​。
对于每一名学生, 请你计算他至少还要再刷多少道题, 才能使得全班刷题 比他多的学生数不超过刷题比他少的学生数。

2.输入格式

第一行包含一个正整数 $N$ 。

第二行包含 $N$ 个整数: A1, A2, A3, … , AN A_{1}, A_{2}, A_{3}, \ldots, A_{N}A1​,A2​,A3​,…,AN​。

3.输出格式

输出 $N$ 个整数, 依次表示第 $1\dots N$ 号学生分别至少还要再刷多少道题。

4.样例输入

5
12 10 15 20 6

5.样例输出

0 3 0 0 7

6.数据范围

$1\le N\le 100000,0\le Ai\le 100000$

7.原图链接

最少刷题数

2.解题思路

这道题应该是可以使用中位数的办法来解决的，但感觉不太好写，并不推荐写。所以考虑一个更加好写的办法——二分。
对于一个刷题数量为 $a[i]$ 的同学，它增加后的刷题量应该在区间 $[a[i],100000]$，为了使得比他刷题多的学生不超过比他刷题少的学生，我们当然希望他刷的题越多越好，如果当他刷了 $x$ 道题是符合要求的，那么大于 $x$ 的答案也一定符合，但是小于 $x$ 的答案却不一定符合，这就满足我们的二段性质，说明我们对于每一位同学都可以去二分答案。

当然二分答案我们还有一个需求，需要快速查询在一段分数区间有多少位同学，我们可以使用数组cnt[i]统计分数为i的同学有多少位，然后将其变为前缀和数组即可。

二分判断时如果当前同学不需要额外刷题即符合要求，我们输出0即可。在二分判断时，当它的刷题数变为 $x$ 时，比他刷题多的同学数量就应该是cnt[100000]-cnt[x]，比他刷题少的同学数量为cnt[x-1]-1。特别注意当 a[i]等于0时比它少的同学数量一定为0需要进行特判（感谢评论区小伙伴的hack）。

为什么还需要减去1呢？因为这位同学原先的刷题数是小于x的， 此时他已经变为x了，所以统计比他少刷题数的同学时需要把他去掉。这样二分得到的答案是他的目标刷题量，减去他本身的刷题量即是答案。

时间复杂度:$O(nlogn)$

Ac_code

C++

#includeusing namespace std;typedef long long LL;typedef unsigned long long uLL;typedef pair<int, int> PII;#define pb(s) push_back(s);#define SZ(s) ((int)s.size());#define ms(s,x) memset(s, x, sizeof(s))#define all(s) s.begin(),s.end()const int inf = 0x3f3f3f3f;const int mod = 1000000007;const int N = 200010;int n;int a[N];int cnt[N];void solve(){cin >> n;for (int i = 0; i < n; ++i) {cin >> a[i];cnt[a[i]]++;}for (int i = 1; i <= 100000; ++i) {cnt[i] += cnt[i - 1];}for (int i = 0; i < n; ++i) {if (cnt[100000] - cnt[a[i]] <= (a[i] == 0 ? 0 : cnt[a[i] - 1])) {cout << 0 << " ";continue;}int l = a[i] + 1, r = 100000;while (l < r) {int mid = l + r >> 1;if (cnt[100000] - cnt[mid] <= cnt[mid - 1] - 1) r = mid;else l = mid + 1;}cout << r - a[i] << " ";}}int main(){ios_base :: sync_with_stdio(false);cin.tie(nullptr);int t = 1;while (t--){solve();}return 0;}

Java

import java.io.*;public class Main{static int N = 200010;static int[] a = new int[N], cnt = new int[N];static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));public static void main(String[] args) throws IOException {int n=Integer.parseInt(br.readLine());String[] s = br.readLine().split(" ");for (int i = 0; i < n; i++) {a[i] = Integer.parseInt(s[i]);cnt[a[i]]++;}for (int i = 1; i <= 100000; ++i) {cnt[i] += cnt[i - 1];}for (int i = 0; i < n; ++i) {if (cnt[100000] - cnt[a[i]] <=(a[i] == 0 ? 0 : cnt[a[i] - 1])) {out.print(0 + " ");continue;}int l = a[i] + 1, r = 100000;while (l < r) {int mid = l + r >> 1;if (cnt[100000] - cnt[mid] <= cnt[mid - 1] - 1) r = mid;else l = mid + 1;}out.print((r - a[i]) + " ");}out.flush();}}