1.最少刷題數(shù)

1.題目描述

小藍(lán)老師教的編程課有 $N$ 名學(xué)生, 編號(hào)依次是 $1\dots N$ 。第 $i$ 號(hào)學(xué)生這學(xué)期 刷題的數(shù)量是 $A_i$。
對(duì)于每一名學(xué)生, 請(qǐng)你計(jì)算他至少還要再刷多少道題, 才能使得全班刷題 比他多的學(xué)生數(shù)不超過(guò)刷題比他少的學(xué)生數(shù)。

2.輸入格式

第一行包含一個(gè)正整數(shù) $N$ 。

第二行包含 $N$ 個(gè)整數(shù): $A_1,A_2,A_3,\dots ,A_N$。

3.輸出格式

輸出 $N$ 個(gè)整數(shù), 依次表示第 $1\dots N$ 號(hào)學(xué)生分別至少還要再刷多少道題。

4.樣例輸入

5
12 10 15 20 6

5.樣例輸出

0 3 0 0 7

6.數(shù)據(jù)范圍

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

7.原圖鏈接

最少刷題數(shù)

2.解題思路

這道題應(yīng)該是可以使用中位數(shù)的辦法來(lái)解決的，但感覺(jué)不太好寫(xiě)，并不推薦寫(xiě)。所以考慮一個(gè)更加好寫(xiě)的辦法——二分。
對(duì)于一個(gè)刷題數(shù)量為 $a[i]$ 的同學(xué)，它增加后的刷題量應(yīng)該在區(qū)間 $[a[i],100000]$，為了使得比他刷題多的學(xué)生不超過(guò)比他刷題少的學(xué)生，我們當(dāng)然希望他刷的題越多越好，如果當(dāng)他刷了 $x$ 道題是符合要求的，那么大于 $x$ 的答案也一定符合，但是小于 $x$ 的答案卻不一定符合，這就滿(mǎn)足我們的二段性質(zhì)，說(shuō)明我們對(duì)于每一位同學(xué)都可以去二分答案。

當(dāng)然二分答案我們還有一個(gè)需求，需要快速查詢(xún)?cè)谝欢畏謹(jǐn)?shù)區(qū)間有多少位同學(xué)，我們可以使用數(shù)組cnt[i]統(tǒng)計(jì)分?jǐn)?shù)為i的同學(xué)有多少位，然后將其變?yōu)榍熬Y和數(shù)組即可。

二分判斷時(shí)如果當(dāng)前同學(xué)不需要額外刷題即符合要求，我們輸出0即可。在二分判斷時(shí)，當(dāng)它的刷題數(shù)變?yōu)?$x$ 時(shí)，比他刷題多的同學(xué)數(shù)量就應(yīng)該是cnt[100000]-cnt[x]，比他刷題少的同學(xué)數(shù)量為cnt[x-1]-1。特別注意當(dāng) a[i]等于0時(shí)比它少的同學(xué)數(shù)量一定為0需要進(jìn)行特判（感謝評(píng)論區(qū)小伙伴的hack）。

為什么還需要減去1呢？因?yàn)檫@位同學(xué)原先的刷題數(shù)是小于x的， 此時(shí)他已經(jīng)變?yōu)?code>x了，所以統(tǒng)計(jì)比他少刷題數(shù)的同學(xué)時(shí)需要把他去掉。這樣二分得到的答案是他的目標(biāo)刷題量，減去他本身的刷題量即是答案。

時(shí)間復(fù)雜度:$O(nlogn)$文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-408794.html

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();
    }
}

到了這里，關(guān)于第十三屆藍(lán)橋杯 Java B 組省賽 D 題—— 最少刷題數(shù)（AC）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！