哪里网站可以做微信头像,网站备案用座机租用,徐州网站建设找哪家,如何设置网站根目录蓝桥杯上岸每日N题第四期 ❗️ ❗️ ❗️
最少刷题数
同步收录 #x1f447;
蓝桥杯上岸必背#xff01;#xff01;#xff01;(持续更新中~)
大家好 我是寸铁#x1f4aa;
冲刺蓝桥杯省一模板大全来啦 #x1f525;
蓝桥杯4月8号就要开始了 #x1f64f;
距离蓝…蓝桥杯上岸每日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 i0;in;i){int asc.nextInt();
}
for(int i1;iN;i){s[i]s[i-1];}
二分
(1)情况1
int l down, r up
while(lr){int midlr;if(q[mid]x)rmid;else lmid1;}
(2)情况2
int l down, r up
while(lr){int midlr11;if(q[mid]x)lmid;else rmid-1;
}最少刷题数
题目描述
对于每一名学生请你计算他至少还要再刷多少道题才能使得全班刷题比他多的学生数不超过刷题比他少的学生数。 全班刷题比他多的学生数不超过刷题比他少的学生数。 换句话说全班刷题比他少的学生数(大于等于)全班刷题比他多的学生数
思路
不会就枚举挨个去模拟样例打暴力 题目是死的人是活的。 12 比他少的610 比他多的1520 需要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 我们需要继续寻找缩小范围即**rmid;** 直到找到最少满足条件的刷题数二分停止。 其他的说明刷题数量不够则需要往刷题数多的方向继续找 lmid1
二分到最**后lr说明找到最少应该刷的总题数** 需要刷的题数(答案)应该刷的题数l-原本的题数p[i] 即**l-p[i]**
为什么需要减1
因为,本来刷题数是小于**mid的,包含在mid-1中。 现在变为mid所以需要减去之前在mid-1**区间的自己。
注意
感谢执梗大佬的提醒 当**a[i]等于0时,即刷题数为0时,班级中不存在比他刷题还少的。 这里我们在二分时,刷题人数比他少的需要进行特判,和0取一个max**。
Accode
import java.io.*;
public class Main{static int N100010,M100000;//N开100010防止数组越界//M开100000刷题数最多是100000static int p[]new int[N];//每个人的刷题数量static int cnt[]new int[N];//统计不同的刷题数量的人数public static void main(String []args) throws IOException{BufferedReader bfnew BufferedReader(new InputStreamReader(System.in));PrintWriter pwnew PrintWriter(new OutputStreamWriter(System.out));int nInteger.parseInt(bf.readLine()); String s[]bf.readLine().split( );for(int i0;in;i) {p[i]Integer.parseInt(s[i]);//每个人的刷题数量cnt[p[i]];//统计 刷题数量为p[i]的人数}//某段刷题数区间内的人数for(int i1;iM;i) {cnt[i]cnt[i-1];}for(int i0;in;i) {//枚举每个学生的刷题数是否满足 if(cnt[M]-cnt[p[i]]cnt[Math.max(0, p[i]-1)]) {//注意边界最少不能少于0道刷题数//刷题比他多的人数小于等于刷题比他少的//那么他就不需要再刷题直接输出0即可pw.print(0 );continue; }//二分出的刷题数量midint lp[i],rM;while(lr) {int midlr1;//二分出的刷题数量if(cnt[M]-cnt[mid]cnt[mid-1]-1) {//刷题数量比他多的学生小于等于刷题数量比他少的学生//进一步减少刷题数量rmidrmid;}else {//否则说明刷题数量不够需要多刷题目lmid1;}}//二分出的l(r)是每个p[i]最少应该刷的总题数//需要刷的题数最少应该刷的总题数-原本的题数//即l-p[i]pw.print((l-p[i]) );}pw.flush();}
}参考资源
https://zhigeng.blog.csdn.net/article/details/128014661?spm1001.2014.3001.5502 ✨ ✨ ✨ 看到这里不妨点个关注
