当前位置: 首页 > news >正文

蓝桥杯上岸每日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刷题数最多是100000static 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;   }//二分出的刷题数量midint l=p[i],r=M;while(l<r) {int mid=l+r>>1;//二分出的刷题数量if(cnt[M]-cnt[mid]<=cnt[mid-1]-1) {//刷题数量比他多的学生小于等于刷题数量比他少的学生//进一步减少刷题数量,r=midr=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
✨ ✨ ✨
看到这里,不妨点个关注 💖

相关文章:

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

蓝桥杯上岸每日N题第四期 ❗️ ❗️ ❗️ 最少刷题数 同步收录 &#x1f447; 蓝桥杯上岸必背&#xff01;&#xff01;&#xff01;(持续更新中~) 大家好 我是寸铁&#x1f4aa; 冲刺蓝桥杯省一模板大全来啦 &#x1f525; 蓝桥杯4月8号就要开始了 &#x1f64f; 距离蓝…...

STM32 LWIP UDP 一对一 一对多发送

STM32 LWIP UDP通信 前言设置 IP 地址UDP函数配置实验结果单播发送&#xff0c;一对一发送广播发送&#xff0c;一对多发送 可能遇到的问题总结 前言 之前没有接触过网络的通信&#xff0c;工作需要 UDP 接收和发送通信&#xff0c;在网上没有找到一对一、一对多的相关例程&am…...

【有趣的设计模式】23 种设计模式详解和场景分析

前言 七大设计原则 1、单一原则&#xff1a;一个类只负责一个职责 2、开闭原则&#xff1a;对修改关闭&#xff0c;对扩展开放 3、里氏替换原则&#xff1a;不要破坏继承关系 4、接口隔离原则&#xff1a;暴露最小接口&#xff0c;避免接口过于臃肿 5、依赖倒置原则&#xff1…...

【数据结构与算法】TypeScript 实现图结构

class Grapg<T> {// 用于存储所有的顶点verteces: T[] [];// 用于存储所有的边 采用邻接表的形式adjList: Map<T, T[]> new Map();// 添加顶点addVertex(v: T) {this.verteces.push(v);// 初始化顶点的邻接表this.adjList.set(v, []);}// 添加边addEdge(v: T, w:…...

《golang设计模式》第一部分·创建型模式-04-抽象工厂模式(Abstract Factory)

文章目录 1. 概述1.1 角色1.2 类图 2. 代码示例2.1 设计2.2 代码2.3 类图 1. 概述 1.1 角色 AbstractFactory&#xff08;抽象工厂&#xff09;&#xff1a;它声明了一组用于创建产品的方法&#xff0c;每一个方法对应一种产品。ConcreteFactory&#xff08;具体工厂&#xf…...

改进粒子群算法优化BP神经网络---回归+分类两种案例

今天采用改进的粒子群算法(LPSO)优化算法优化BP神经网络。本文选用的LPSO算法是之前作者写过的一篇文章&#xff1a;基于改进莱维飞行和混沌映射&#xff08;10种混沌映射随意切换&#xff09;的粒子群优化算法&#xff0c;附matlab代码 文章一次性讲解两种案例&#xff0c;回归…...

VSCode和QT联合开发

提示&#xff1a;本文为学习记录&#xff0c;若有错误&#xff0c;请联系作者&#xff0c;谦虚受教。 文章目录 前言一、VSCODE下载二、使用步骤1.下载扩展 二、新建工程1.新建文件夹2.新建工程3.UI界面文件操作4.效果 总结 前言 一、VSCODE下载 下载地址 二、使用步骤 1.下…...

YOLO5-1 使用YOLO5检测 水面漂浮物记录

一 数据集 robflow 漂浮物数据集&#xff1a;buoy Computer Vision Dataset by ai 二 YOLO5管网 yolo5 :https://github.com/ultralytics/yolov5 克隆代码&#xff1a; git clone https://github.com/ultralytics/yolov5 # clone cd yolov5 pip install -r requirements.…...

MongoDB教程-7

正如在MongoDB关系的最后一章中所看到的&#xff0c;为了在MongoDB中实现规范化的数据库结构&#xff0c;我们使用了引用关系的概念&#xff0c;也被称为手动引用&#xff0c;在这个概念中&#xff0c;我们手动将被引用文档的id存储在其他文档中。然而&#xff0c;在一个文档包…...

Redisson提供优秀的并发控制机制

1. JDK集合类 对于JDK的集合类&#xff0c;forEach方法其实并不能完全避免并发修改异常。 forEach本质上还是一个循环遍历&#xff0c;如果在循环体内直接对集合进行修改&#xff0c;仍然会产生ConcurrentModificationException。 例如&#xff1a; List<String> lis…...

Linux: 设置qmake的Qt版本

Qt开发&#xff0c;qmake会对应一个Qt版本&#xff0c;有时候需要切换这个版本&#xff0c;例如把qmake从Qt5.12切换到Qt5.9, 怎么操作呢&#xff1f; 案例如下&#xff1a; 银河麒麟V10系统&#xff0c;下载安装了Qt5.9.8&#xff0c;但是检查qmake发现它使用的是5.12.8&…...

使用LLM插件从命令行访问Llama 2

大家好&#xff0c;最近的一个大新闻是Meta AI推出了新的开源授权的大型语言模型Llama 2&#xff0c;这是一项非常重要的进展。Facebook最初的LLaMA模型于今年2月发布&#xff0c;掀起了开源LLM领域的创新浪潮——从微调变体到从零开始的再创造。 如果在Llama 2版本发布之日&a…...

gateway过滤器没生效,特殊原因

看这边文章的前提&#xff0c;你要会gateway&#xff0c;知道过滤器怎么配置&#xff1f; 直接来看过滤器&#xff0c;局部过滤器 再来看配置 请求路径 http://127.0.0.1:8080/appframework/services/catalog/catalogSpecials.json?pageindex1&pagesize10&pkidd98…...

长相思追剧小游戏

看效果图 Vue长相思 刚学Vue&#xff0c;正好在追剧&#xff0c;看到这个小案例觉得挺好玩的&#xff0c;第一天学&#xff0c;代码太简陋了 代码 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name&qu…...

leetcode做题笔记51

按照国际象棋的规则&#xff0c;皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 n 皇后问题 研究的是如何将 n 个皇后放置在 nn 的棋盘上&#xff0c;并且使皇后彼此之间不能相互攻击。 给你一个整数 n &#xff0c;返回所有不同的 n 皇后问题 的解决方案。 每一种…...

Windows同时安装两个版本的JDK并随时切换,以JDK6和JDK8为例,并解决相关存在的问题(亲测有效)

Windows同时安装两个版本的JDK并随时切换&#xff0c;以JDK6和JDK8为例&#xff0c;并解决相关存在的问题&#xff08;亲测有效&#xff09; 1.下载不同版本JDK 这里给出JDK6和JDK的百度网盘地址&#xff0c;具体安装过程&#xff0c;傻瓜式安装即可。 链接&#xff1a;http…...

【ChatGPT辅助学Rust | 基础系列 | Cargo工具】Cargo介绍及使用

文章目录 前言一&#xff0c;Cargo介绍1&#xff0c;Cargo安装2&#xff0c;创建Rust项目2&#xff0c;编译项目&#xff1a;3&#xff0c;运行项目&#xff1a;4&#xff0c;测试项目&#xff1a;5&#xff0c;更新项目的依赖&#xff1a;6&#xff0c;生成项目的文档&#xf…...

全面了解CPU Profiler:解读CPU性能分析工具的核心功能与用法

关于作者&#xff1a;CSDN内容合伙人、技术专家&#xff0c; 从零开始做日活千万级APP。 专注于分享各领域原创系列文章 &#xff0c;擅长java后端、移动开发、人工智能等&#xff0c;希望大家多多支持。 目录 一、导读二、概览三、使用3.1 通过调用系统API3.2 通过Android Stu…...

rust format!如何转义{},输出{}?

在Rust中&#xff0c;如果你想要在字符串中包含花括号 {} &#xff0c;你需要使用双花括号 {{}} 来进行转义。这是因为单个花括号 {} 在字符串中表示占位符&#xff0c;用于格式化字符串。 以下是一个示例&#xff1a; fn main() {let text "这是一个示例&#xff1a; {…...

真人AI写真的制作方法-文生图换脸

AI写真最近火起来了&#xff0c;特别是某款现象级相机的出现&#xff0c;只需要上传自己的照片&#xff0c;就能生成漂亮的写真照&#xff0c;这一产品再次带火了AI绘画。今天我就来分享一个使用Stable Diffusion WebUI制作真人AI写真的方法&#xff0c;不用训练&#xff0c;快…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

Java多线程实现之Callable接口深度解析

Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...

ios苹果系统,js 滑动屏幕、锚定无效

现象&#xff1a;window.addEventListener监听touch无效&#xff0c;划不动屏幕&#xff0c;但是代码逻辑都有执行到。 scrollIntoView也无效。 原因&#xff1a;这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作&#xff0c;从而会影响…...

Java面试专项一-准备篇

一、企业简历筛选规则 一般企业的简历筛选流程&#xff1a;首先由HR先筛选一部分简历后&#xff0c;在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如&#xff1a;Boss直聘&#xff08;招聘方平台&#xff09; 直接按照条件进行筛选 例如&#xff1a…...

项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)

Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败&#xff0c;具体原因是客户端发送了密码认证请求&#xff0c;但Redis服务器未设置密码 1.为Redis设置密码&#xff08;匹配客户端配置&#xff09; 步骤&#xff1a; 1&#xff09;.修…...

算法岗面试经验分享-大模型篇

文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer &#xff08;1&#xff09;资源 论文&a…...

如何更改默认 Crontab 编辑器 ?

在 Linux 领域中&#xff0c;crontab 是您可能经常遇到的一个术语。这个实用程序在类 unix 操作系统上可用&#xff0c;用于调度在预定义时间和间隔自动执行的任务。这对管理员和高级用户非常有益&#xff0c;允许他们自动执行各种系统任务。 编辑 Crontab 文件通常使用文本编…...

为什么要创建 Vue 实例

核心原因:Vue 需要一个「控制中心」来驱动整个应用 你可以把 Vue 实例想象成你应用的**「大脑」或「引擎」。它负责协调模板、数据、逻辑和行为,将它们变成一个活的、可交互的应用**。没有这个实例,你的代码只是一堆静态的 HTML、JavaScript 变量和函数,无法「活」起来。 …...

Python实现简单音频数据压缩与解压算法

Python实现简单音频数据压缩与解压算法 引言 在音频数据处理中&#xff0c;压缩算法是降低存储成本和传输效率的关键技术。Python作为一门灵活且功能强大的编程语言&#xff0c;提供了丰富的库和工具来实现音频数据的压缩与解压。本文将通过一个简单的音频数据压缩与解压算法…...

【Kafka】Kafka从入门到实战:构建高吞吐量分布式消息系统

Kafka从入门到实战:构建高吞吐量分布式消息系统 一、Kafka概述 Apache Kafka是一个分布式流处理平台,最初由LinkedIn开发,后成为Apache顶级项目。它被设计用于高吞吐量、低延迟的消息处理,能够处理来自多个生产者的海量数据,并将这些数据实时传递给消费者。 Kafka核心特…...