蓝桥杯上岸每日N题第四期 ❗️ ❗️ ❗️
最少刷题数
同步收录 👇
蓝桥杯上岸必背!!!(持续更新中~)
大家好 我是寸铁💪
冲刺蓝桥杯省一模板大全来啦 🔥
蓝桥杯4月8号就要开始了 🙏
距离蓝桥杯省赛倒数第3天 ❗️ ❗️ ❗️
还没背熟模板的伙伴们背起来 💪 💪 💪
真题千千万万遍,蓝桥省一自然现! ✌️
日更3000里,蓝桥眷顾你 🌟
祝大家4月8号蓝桥杯上岸 ☀️ ~
还没背熟模板的伙伴们背起来 💪 💪 💪
祝大家4月8号蓝桥杯上岸 ☀️
不清楚蓝桥杯考什么的点点下方👇
考点秘籍
想背纯享模版的伙伴们点点下方👇
蓝桥杯省一你一定不能错过的模板大全(第一期)
蓝桥杯省一你一定不能错过的模板大全(第二期)
蓝桥杯省一你一定不能错过的模板大全(第三期)
蓝桥杯省一你一定不能错过的模板大全(第四期)!!!
想背注释模版的伙伴们点点下方👇
蓝桥杯必背第一期
蓝桥杯必背第二期
往期精彩回顾
蓝桥杯上岸每日N题 第一期(一)!!!
蓝桥杯上岸每日N题第一期(二)!!!
蓝桥杯上岸每日N题第一期(三)!!!
蓝桥杯上岸每日N题第二期(一)!!!
蓝桥杯上岸每日N题第三期(一)!!!
操作系统期末题库 第九期(完结)
LeetCode Hot100 刷题(第三期)
idea创建SpringBoot项目报错解决方案
数据库SQL语句(期末冲刺)
想看JavaB组填空题的伙伴们点点下方 👇
填空题
竞赛干货
算法竞赛字符串常用操作大全
蓝桥杯上岸必刷!!!(模拟/枚举专题)
蓝桥杯上岸必背!!! (第三期 DP)
蓝桥杯上岸必背!!!(第四期DFS)
蓝桥杯上岸必背!!!(第五期BFS)
蓝桥杯上岸必背!!!(第六期树与图的遍历)
蓝桥杯上岸必背!!!(第七期 最短路算法)
蓝桥杯上岸必背!!!(第八期 简单数论)
分析
考点:前缀和+二分
先背一遍模板:
前缀和:
for(int i=0;i<n;i++){
int a=sc.nextInt();
}
for(int i=1;i<=N;i++){
s[i]+=s[i-1];
}
二分
(1)情况1
int l= down, r= up
while(l<r){
int mid=l+r+;
if(q[mid]>=x)r=mid;
else l=mid+1;
}
(2)情况2
int l= down, r= up
while(l<r){
int mid=l+r+1>>1;
if(q[mid]<=x)l=mid;
else r=mid-1;
}
最少刷题数
题目描述:
对于每一名学生,请你计算他至少还要再刷多少道题,才能使得全班刷题比他多的学生数不超过刷题比他少的学生数。
全班刷题比他多的学生数不超过刷题比他少的学生数。
换句话说:全班刷题比他少的学生数>=(大于等于)全班刷题比他多的学生数
思路
不会就枚举,挨个去模拟样例,打暴力!
题目是死的,人是活的。
12
比他少的:6,10
比他多的:15,20
需要:0
10
比他少的:6
比他多的:12 15 20
需要:3
15
比他少的:6 10 12
比他多的:20
需要:0
20
比他少的:6 10 12 15
比他多的:20
需要:0
6
比他少的:
比他多的:10 12 15 20
需要:7
我们发现:
像10需要多刷3道题,变为13,将6、12包含进来
像6需要多刷7道题,变为13,将10、12包含进来
多刷题一定可以满足条件,但是少刷题不一定满足条件。
发现具有二段性,我们要找到的是最少满足条件的答案!
这时便想到了二分!
我们通过二分去二分出最少应该刷的总题数
怎么二分?
首先要满足的是题目所给的条件:
全班刷题比他少的学生数>=(大于等于)全班刷题比他多的学生数
那我们要怎么知道刷题数的人数?
用**cnt[]
数组存一下每种刷题数的人数**
再用前缀和处理每段刷题数区间的人数
如果全班刷题比他少的学生数>=(大于等于)全班刷题比他多的学生数,说明不需要刷题,那么直接输出0即可。
剩下的情况需要二分:
当前刷题数 mid
比他刷题数量多的人数即:cnt[M]-cnt[mid]
比他刷题数量少的人数即:cnt[mid-1]-1
cnt[mid-1]-1
//当前刷题数为mid
//比他少的便是cnt[mid-1]-1
满足刷题数量比他多的学生小于等于刷题数量比他少的学生cnt[M]-cnt[mid]<=cnt[mid-1]-1
我们需要继续寻找,缩小范围,即**r=mid;
**
直到找到最少满足条件的刷题数,二分停止。
其他的说明刷题数量不够,则需要往刷题数多的方向继续找:l=mid+1
二分到最**后l==r
说明找到最少应该刷的总题数**
需要刷的题数(答案):应该刷的题数l-原本的题数p[i]
即**l-p[i]
**
为什么需要减1?
因为,本来刷题数是小于**mid
的,包含在mid-1
中。
现在变为mid
,所以需要减去之前在mid-1
**区间的自己。
注意:
感谢@执梗大佬的提醒!
当**a[i]
等于0时,即刷题数为0时,班级中不存在比他刷题还少的。
这里我们在二分时,刷题人数比他少的需要进行特判,和0取一个max**。文章来源:https://www.toymoban.com/news/detail-619829.html
Accode
import java.io.*;
public class Main{
static int N=100010,M=100000;
//N开100010防止数组越界
//M开100000刷题数最多是100000
static int p[]=new int[N];//每个人的刷题数量
static int cnt[]=new int[N];//统计不同的刷题数量的人数
public static void main(String []args) throws IOException
{
BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
PrintWriter pw=new PrintWriter(new OutputStreamWriter(System.out));
int n=Integer.parseInt(bf.readLine());
String s[]=bf.readLine().split(" ");
for(int i=0;i<n;i++) {
p[i]=Integer.parseInt(s[i]);
//每个人的刷题数量
cnt[p[i]]++;
//统计 刷题数量为p[i]的人数
}
//某段刷题数区间内的人数
for(int i=1;i<=M;i++) {
cnt[i]+=cnt[i-1];
}
for(int i=0;i<n;i++) {
//枚举每个学生的刷题数是否满足
if(cnt[M]-cnt[p[i]]<=cnt[Math.max(0, p[i]-1)]) {
//注意边界:最少不能少于0道刷题数
//刷题比他多的人数小于等于刷题比他少的
//那么他就不需要再刷题,直接输出0即可
pw.print(0+" ");
continue;
}
//二分出的刷题数量mid
int l=p[i],r=M;
while(l<r) {
int mid=l+r>>1;
//二分出的刷题数量
if(cnt[M]-cnt[mid]<=cnt[mid-1]-1) {
//刷题数量比他多的学生小于等于刷题数量比他少的学生
//进一步减少刷题数量,r=mid
r=mid;
}
else {
//否则,说明刷题数量不够,需要多刷题目
l=mid+1;
}
}
//二分出的l(r)是每个p[i]最少应该刷的总题数
//需要刷的题数:最少应该刷的总题数-原本的题数
//即l-p[i]
pw.print((l-p[i])+" ");
}
pw.flush();
}
}
参考资源
https://zhigeng.blog.csdn.net/article/details/128014661?spm=1001.2014.3001.5502
✨ ✨ ✨
看到这里,不妨点个关注 💖文章来源地址https://www.toymoban.com/news/detail-619829.html
到了这里,关于蓝桥杯上岸每日N题 第四期(最少刷题数)!!!的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!