蓝桥杯上岸每日N题 第四期(最少刷题数)!!!

这篇具有很好参考价值的文章主要介绍了蓝桥杯上岸每日N题 第四期(最少刷题数)!!!。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

蓝桥杯上岸每日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**。

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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 蓝桥杯上岸每日N题 (修剪灌木)

    爱丽丝要完成一项修剪灌木的工作。 有 N 棵灌木整齐的从左到右排成一排。 爱丽丝在每天傍晚会修剪一棵灌木,让灌木的高度变为 0 厘米。 爱丽丝修剪灌木的顺序是从最左侧的灌木开始,每天向右修剪一棵灌木。 当修剪了最右侧的灌木后,她会调转方向,下一天开始向左修

    2024年02月11日
    浏览(34)
  • 蓝桥杯上岸每日N题第一期(二)!!!

    这道题我们可以得出的是二分的结果是满足k块巧克力的最大边长是多少? 题目要求: 1.形状是正方形,边长是整数 2.大小相同 即要求边长均为x 我们就可以确保得到 边长一致的正方形 大小相同即分出的块数为整数, 向下取整!!! 得到能够凑出的整块巧克力 如果分出的块

    2024年02月16日
    浏览(36)
  • 蓝桥杯上岸每日N题 第一期(一)!!!

    2020 年春节期间,有一个特殊的日期引起了大家的注意:2020 年 2 月 2 日。因为如果将这个日期按 “yyyymmdd” 的格式写成一个 8 位数是 20200202,恰好是一个回文数。我们称这样的日期是回文日期。 有人表示 20200202 是 “千年一遇” 的特殊日子。对此小明很不认同,因为不到

    2024年02月16日
    浏览(40)
  • 蓝桥杯上岸每日N题 第七期(小猫爬山)!!!

    要尽可能减少花费--递归的分支尽可能少--优先考虑放重猫 优先考虑放重猫 ,需要从 大到小排个序 , 一直往下搜索,答案是唯一的。 放得下猫就 继续往该车往下加 放不下就再 另外开一辆放猫 分两个分支去放 开一辆继续放其他猫的为一个分支 开另一辆单独只放一只猫的为

    2024年02月14日
    浏览(70)
  • 蓝桥杯上岸每日N题 第八期 (全球变暖)!!!

    其中”上下左右”四个方向上 # 连在一起的一片陆地组成一座岛屿。 具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋 . ),它就会被淹没。 注:图中有3个岛屿,上下连续区域。 注:题中有一个岛屿全被淹没 观察一下:岛屿中陆地的数量和海洋的数量是

    2024年02月14日
    浏览(62)
  • 面试 Java 框架八股文五问五答第四期

    作者:程序员小白条,个人博客 相信看了本文后,对你的面试是有一定帮助的! ⭐点赞⭐收藏⭐不迷路!⭐ 1)什么是设计模式? 设计模式是一套被反复使用、多数人知晓的、经过分类编目的、代码设计经验的总结。它是解决特定场景下常见问题的一种可重用解决方案。设

    2024年02月03日
    浏览(55)
  • JavaScript 手写代码 第四期

    我们在日常开发过程中,往往都是取出来直接用,从来不思考代码的底层实现逻辑,但当我开始研究一些底层的东西的时候,才开始理解了JavaScript每个方法和函数的底层实现思路,我认为这可以很好的提高我们的代码水平和逻辑思维。 简单来说,就是将多维数组转换为一维

    2024年02月10日
    浏览(57)
  • 马蹄集第四期oj

    目录 供水管线 黑客小码哥  逆序 来给单词分类  前k小数(进阶)  前K小数 线段树  队列安排  一元多项式的加法 快排变形 难度:钻石 0时间限制:1秒 巴占用内存:128M 在个城市之间原本要规划修建许多条下水管道,管理人员发现这些管道会形成一条 回路,而下水道只要

    2024年02月07日
    浏览(56)
  • 码银送书第四期《Python之光》

    作为一种极其流行的编程语言,Python已经成为了当今最为重要的生产力工具之一。无论小学生还是各行各业的从业人员,都开始学习Python编程。这种编程语言在许多领域中都有广泛的应用,因此Python编程已经成为了许多职业的必备能力或者加分项。 然而,在市面上的Python入门

    2024年02月15日
    浏览(63)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包