第十三届蓝桥杯 Java B 组省赛 D 题—— 最少刷题数(AC)

1.最少刷题数

1.题目描述

小蓝老师教的编程课有

N

N

N 名学生, 编号依次是

1

N

1…N

1N 。第

i

i

i 号学生这学期 刷题的数量是

A

i

A_{i}

Ai
对于每一名学生, 请你计算他至少还要再刷多少道题, 才能使得全班刷题 比他多的学生数不超过刷题比他少的学生数。

2.输入格式

第一行包含一个正整数

N

N

N

第二行包含

N

N

N 个整数:

A

1

,

A

2

,

A

3

,

,

A

N

A_{1}, A_{2}, A_{3}, ldots, A_{N}

A1,A2,A3,,AN

3.输出格式

输出

N

N

N 个整数, 依次表示第

1

N

1 ldots N

1N 号学生分别至少还要再刷多少道题。

4.样例输入

5
12 10 15 20 6

5.样例输出

0 3 0 0 7

6.数据范围

1

N

100000

,

0

A

i

100000

1≤N≤100000,0≤Ai≤100000

1N100000,0Ai100000

7.原图链接

最少刷题数

2.解题思路

这道题应该是可以使用中位数的办法来解决的,但感觉不太好写,并不推荐写。所以考虑一个更加好写的办法——二分
对于一个刷题数量为

a

[

i

]

a[i]

a[i] 的同学,它增加后的刷题量应该在区间

[

a

[

i

]

,

100000

]

[a[i],100000]

[a[i],100000],为了使得比他刷题多的学生不超过比他刷题少的学生,我们当然希望他刷的题越多越好,如果当他刷了

x

x

x 道题是符合要求的,那么大于

x

x

x 的答案也一定符合,但是小于

x

x

x 的答案却不一定符合,这就满足我们的二段性质,说明我们对于每一位同学都可以去二分答案。

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

二分判断时如果当前同学不需要额外刷题即符合要求,我们输出0即可。在二分判断时,当它的刷题数变为

x

x

x 时,比他刷题多的同学数量就应该是cnt[100000]-cnt[x],比他刷题少的同学数量为cnt[x-1]-1。特别注意当 a[i]等于0时比它少的同学数量一定为0需要进行特判(感谢评论区小伙伴的hack)。

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

时间复杂度:

O

(

n

l

o

g

n

)

O(nlogn)

O(nlogn)

Ac_code

C++

#include<bits/stdc++.h>
using 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();
    }
}

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>