小藍(lán)老師教的編程課有
N
N
N 名學(xué)生, 編號(hào)依次是
1
…
N
1…N
1…N 。第
i
i
i 號(hào)學(xué)生這學(xué)期 刷題的數(shù)量是
A
i
A_{i}
Ai?。
對(duì)于每一名學(xué)生, 請(qǐng)你計(jì)算他至少還要再刷多少道題, 才能使得全班刷題 比他多的學(xué)生數(shù)不超過(guò)刷題比他少的學(xué)生數(shù)。
第一行包含一個(gè)正整數(shù) N N N 。
第二行包含 N N N 個(gè)整數(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 個(gè)整數(shù), 依次表示第 1 … N 1 \ldots N 1…N 號(hào)學(xué)生分別至少還要再刷多少道題。
4.樣例輸入5
12 10 15 20 6
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.解題思路這道題應(yīng)該是可以使用中位數(shù)的辦法來(lái)解決的,但感覺(jué)不太好寫(xiě),并不推薦寫(xiě)。所以考慮一個(gè)更加好寫(xiě)的辦法——二分。
對(duì)于一個(gè)刷題數(shù)量為
a
[
i
]
a[i]
a[i] 的同學(xué),它增加后的刷題量應(yīng)該在區(qū)間
[
a
[
i
]
,
100000
]
[a[i],100000]
[a[i],100000],為了使得比他刷題多的學(xué)生不超過(guò)比他刷題少的學(xué)生,我們當(dāng)然希望他刷的題越多越好,如果當(dāng)他刷了
x
x
x 道題是符合要求的,那么大于
x
x
x 的答案也一定符合,但是小于
x
x
x 的答案卻不一定符合,這就滿足我們的二段性質(zhì),說(shuō)明我們對(duì)于每一位同學(xué)都可以去二分答案。
當(dāng)然二分答案我們還有一個(gè)需求,需要快速查詢?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
x
x 時(shí),比他刷題多的同學(xué)數(shù)量就應(yīng)該是cnt[100000]-cnt[x]
,比他刷題少的同學(xué)數(shù)量為cnt[x-1]-1
。
為什么還需要減去1
呢?因?yàn)檫@位同學(xué)原先的刷題數(shù)是小于x
的, 此時(shí)他已經(jīng)變?yōu)?code>x了,所以統(tǒng)計(jì)比他少刷題數(shù)的同學(xué)時(shí)需要把他去掉。這樣二分得到的答案是他的目標(biāo)刷題量,減去他本身的刷題量即是答案。
時(shí)間復(fù)雜度: 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;
}
Javaimport 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)定的海外服務(wù)器提供商?創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源,準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性,企業(yè)級(jí)服務(wù)器適合批量采購(gòu),新人活動(dòng)首月15元起,快前往官網(wǎng)查看詳情吧
網(wǎng)站欄目:第十三屆JavaB組省賽D題——最少刷題數(shù)(AC)-創(chuàng)新互聯(lián)
URL網(wǎng)址:http://bm7419.com/article26/dioijg.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供用戶體驗(yàn)、云服務(wù)器、營(yíng)銷型網(wǎng)站建設(shè)、網(wǎng)頁(yè)設(shè)計(jì)公司、搜索引擎優(yōu)化、面包屑導(dǎo)航
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請(qǐng)盡快告知,我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如需處理請(qǐng)聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時(shí)需注明來(lái)源: 創(chuàng)新互聯(lián)
猜你還喜歡下面的內(nèi)容