1.最少刷题数
1.题目描述
小蓝老师教的编程课有
N
N
N 名学生, 编号依次是
1
…
N
1…N
1…N 。第
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
1…N 号学生分别至少还要再刷多少道题。
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
1≤N≤100000,0≤Ai≤100000
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。
为什么还需要减去1呢？因为这位同学原先的刷题数是小于x的， 此时他已经变为x了，所以统计比他少刷题数的同学时需要把他去掉。这样二分得到的答案是他的目标刷题量，减去他本身的刷题量即是答案。
时间复杂度:
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();
}
}
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
当前标题：第十三届JavaB组省赛D题——最少刷题数（AC）-创新互联
文章转载：
http://cdkjz.cn/article/dioijg.html
