1.最少刷題數(shù) 1.題目描述

小藍老師教的編程課有 N N N 名學生, 編號依次是 1 … N 1…N 1…N 。第 i i i 號學生這學期 刷題的數(shù)量是 A i A_{i} Ai?。
對于每一名學生, 請你計算他至少還要再刷多少道題, 才能使得全班刷題 比他多的學生數(shù)不超過刷題比他少的學生數(shù)。

網(wǎng)站建設哪家好，找創(chuàng)新互聯(lián)公司！專注于網(wǎng)頁設計、網(wǎng)站建設、微信開發(fā)、重慶小程序開發(fā)公司、集團企業(yè)網(wǎng)站建設等服務項目。為回饋新老客戶創(chuàng)新互聯(lián)還提供了偏關(guān)免費建站歡迎大家使用！2.輸入格式

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

第二行包含 N N N 個整數(shù): 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 個整數(shù), 依次表示第 1 … N 1 \ldots N 1…N 號學生分別至少還要再刷多少道題。

4.樣例輸入

5
12 10 15 20 6

5.樣例輸出

0 3 0 0 7

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

1 ≤ N ≤ 100000 , 0 ≤ A i ≤ 100000 1≤N≤100000,0≤Ai≤100000 1≤N≤100000,0≤Ai≤100000

7.原圖鏈接

最少刷題數(shù)

2.解題思路

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

當然二分答案我們還有一個需求，需要快速查詢在一段分數(shù)區(qū)間有多少位同學，我們可以使用數(shù)組cnt[i]統(tǒng)計分數(shù)為i的同學有多少位，然后將其變?yōu)榍熬Y和數(shù)組即可。

二分判斷時如果當前同學不需要額外刷題即符合要求，我們輸出0即可。在二分判斷時，當它的刷題數(shù)變?yōu)? x x x 時，比他刷題多的同學數(shù)量就應該是cnt[100000]-cnt[x]，比他刷題少的同學數(shù)量為cnt[x-1]-1。

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

時間復雜度: O ( n l o g n ) O(nlogn) O(nlogn)

Ac_code C++

#includeusing namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pairPII;
#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]]<= cnt[max(0,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]]<= cnt[Math.max(0,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();
    }
}

你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)站欄目：第十三屆JavaB組省賽D題——最少刷題數(shù)（AC）-創(chuàng)新互聯(lián)
URL網(wǎng)址：http://jinyejixie.com/article26/dioijg.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供用戶體驗、云服務器、營銷型網(wǎng)站建設、網(wǎng)頁設計公司、搜索引擎優(yōu)化、面包屑導航

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)