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

蓝桥杯每日一题:牛的学术圈I(二分,双指针)

由于对计算机科学的热爱,以及有朝一日成为 「Bessie 博士」的诱惑,奶牛 Bessie 开始攻读计算机科学博士学位。

经过一段时间的学术研究,她已经发表了 N篇论文,并且她的第 i 篇论文得到了来自其他研究文献的 ci次引用。

Bessie 听说学术成就可以用 ℎ 指数来衡量。

hℎ 指数等于使得研究员有至少 ℎ 篇引用次数不少于 hℎ 的论文的最大整数 hℎ。

例如,如果一名研究员有 4 篇论文,引用次数分别为 (1,100,2,3),则 hℎ 指数为 2,然而若引用次数为 (1,100,3,3) 则 hℎ 指数将会是 3。

为了提升她的 hℎ 指数,Bessie 计划写一篇综述,并引用一些她曾经写过的论文。

由于页数限制,她至多可以在这篇综述中引用 L篇论文,并且她只能引用每篇她的论文至多一次

请帮助 Bessie 求出在写完这篇综述后她可以达到的最大 hℎ 指数。

注意 Bessie 的导师可能会告知她纯粹为了提升 hℎ 指数而写综述存在违反学术道德的嫌疑;我们不建议其他学者模仿 Bessie 的行为。

输入格式

输入的第一行包含 N和 L。

第二行包含 N 个空格分隔的整数 c1,…,cn。

输出格式

输出写完综述后 Bessie 可以达到的最大 hℎ 指数。

数据范围

1≤N≤10^5,
0≤ci≤10^5,
0≤L≤10^5

输入样例1:
4 0
1 100 2 3
输出样例1:
2
样例1解释

Bessie 不能引用任何她曾经写过的论文。上文中提到,(1,100,2,3)的 hℎ 指数为 22。

输入样例2:
4 1
1 100 2 3
输出样例2:
3

如果 Bessie 引用她的第三篇论文,引用数会变为 (1,100,3,3)。上文中提到,这一引用数的 hℎ 指数为 3。

解题思路:

二分:

从0-n二分枚举每个h的值,取check:统计论文中>=h的个数为 a,和==h-1 的个数b;

检查a+min(L,b)是否>=h

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;
const int N = 1e5+10;
int w[N];
int n,L;bool check(int mid)
{int a = 0,b = 0;for(int i=0;i<n;i++){if(w[i]>=mid) a++;if(w[i]==mid-1) b++;}return a + min(L,b) >= mid;
}int main()
{cin>>n>>L;for(int i=0;i<n;i++) cin>>w[i];int l = 0,r = n;while(l<r){int mid = l + r + 1 >> 1;if(check(mid)) l = mid;else r = mid - 1;}printf("%d\n",r);return 0;
}

双指针:

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 100010;int n, L;
int w[N];int main()
{scanf("%d%d", &n, &L);for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);sort(w + 1, w + n + 1, greater<int>());int res = 0;for (int i = 1, j = n; i <= n; i ++ ){while (j && w[j] < i) j -- ;if (w[i] >= i - 1 && i - j <= L)res = i;}printf("%d\n", res);return 0;
}作者:yxc
链接:https://www.acwing.com/activity/content/code/content/7939954/
来源:AcWing。

相关文章:

蓝桥杯每日一题:牛的学术圈I(二分,双指针)

由于对计算机科学的热爱&#xff0c;以及有朝一日成为 「Bessie 博士」的诱惑&#xff0c;奶牛 Bessie 开始攻读计算机科学博士学位。 经过一段时间的学术研究&#xff0c;她已经发表了 N篇论文&#xff0c;并且她的第 i 篇论文得到了来自其他研究文献的 ci次引用。 Bessie 听…...

fping命令

fping是一个用于网络扫描的工具&#xff0c;它可以在 Linux 系统上使用。fping可以发送 ICMP ECHO_REQUEST&#xff08;即 ping&#xff09;数据包到指定的网络地址范围&#xff0c;并等待响应。通过这种方式&#xff0c;fping可以用来检测哪些 IP 地址是活跃的。 可以测试多个…...

奇富科技推出新一代全自研智能语音模型,打破沟通壁垒

“您好&#xff01;请问是李先生噻&#xff1f;” 李先生刚接起电话&#xff0c;就被这熟悉的乡音逗乐了。这不是他所预料的常规客服&#xff0c;而是奇富科技新一代全自研智能语音模型——QI语精灵。这款模型不仅能用方言与人自然交流&#xff0c;还能在智能营销、贷后提醒、风…...

穿越代码之海:探寻结构体深层逻辑,展望未来应用新天地

欢迎来到白刘的领域 Miracle_86.-CSDN博客 系列专栏 C语言知识 先赞后看&#xff0c;已成习惯 创作不易&#xff0c;多多支持&#xff01; 结构体作为一种数据结构&#xff0c;其定义和特点决定了它在各种应用中的广泛适用性。随着科技的进步和新兴行业的不断涌现&#xf…...

layui框架实战案例(26):layui-carousel轮播组件添加多个Echarts图标的效果

在Layui中&#xff0c;使用layui-carousel轮播组件嵌套Echarts图表来实现多个图表的展示。 css层叠样式表 调整轮播图背景色为白色&#xff1b;调整当个Echarts图表显示loading…状态&#xff1b;同一个DIV轮播项目添加多个Echarts的 .layui-carousel {background-color: #f…...

Unity开发一个FPS游戏之三

在前面的两篇博客中&#xff0c;我已实现了一个FPS游戏的大部分功能&#xff0c;包括了第一人称的主角运动控制&#xff0c;武器射击以及敌人的智能行为。这里我将继续完善这个游戏&#xff0c;包括以下几个方面&#xff1a; 增加一个真实的游戏场景&#xff0c;模拟一个废弃的…...

NIUSHOP完美运营版商城 虚拟商品全功能商城 全能商城小程序 智慧商城系统 全品类百货商城

完美运营版商城/拼团/团购/秒杀/积分/砍价/实物商品/虚拟商品等全功能商城 干干净净 没有一丝多余收据 还没过手其他站 还没乱七八走的广告和后门 后台可以自由拖曳修改前端UI页面 还支持虚拟商品自动发货等功能 挺不错的一套源码 前端UNIAPP 后端PHP 一键部署版本 源码免费…...

vue2开发好还是vue3开发好vue3.0开发路线

Vue 2和Vue 3都是流行的前端框架&#xff0c;它们各自有一些特点和优势。选择Vue 2还是Vue 3进行开发&#xff0c;主要取决于你的项目需求、团队的技术栈、以及对新特性的需求等因素。以下是一些关于Vue 2和Vue 3的比较&#xff0c;帮助你做出决策&#xff1a; Vue 2&#xff1…...

爬虫 新闻网站 并存储到CSV文件 以红网为例 V2.0 (控制台版)升级自定义查询关键词、时间段,详细注释

爬虫&#xff1a;红网网站&#xff0c; 获取指定关键词与指定时间范围内的新闻&#xff0c;并存储到CSV文件 V2.0&#xff08;控制台版&#xff09; 爬取目的&#xff1a;为了获取某一地区更全面的在红网已发布的宣传新闻稿&#xff0c;同时也让自己的工作更便捷 对比V1.0升级的…...

JavaSE-11笔记【多线程2(+2024新)】

文章目录 6.线程安全6.1 线程安全问题6.2 线程同步机制6.3 关于线程同步的面试题6.3.1 版本16.3.2 版本26.3.3 版本36.3.4 版本4 7.死锁7.1 多线程卖票问题 8.线程通信8.1 wait()和sleep的区别&#xff1f;8.2 两个线程交替输出8.3 三个线程交替输出8.4 线程通信-生产者和消费者…...

WebKit是什么?

WebKit是一个开源的浏览器引擎&#xff0c;它用于呈现网页内容在许多现代浏览器中&#xff0c;包括Safari浏览器、iOS内置浏览器、以及一些其他浏览器如Google Chrome的早期版本。以下是一些关于WebKit的重要信息&#xff1a; 起源和发展&#xff1a;WebKit最初是由苹果公司为其…...

谷歌(Google)历年编程真题——接雨水

谷歌历年面试真题——数组和字符串系列真题练习。 接雨水 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图&#xff0c;计算按此排列的柱子&#xff0c;下雨之后能接多少雨水。 示例 1&#xff1a; 输入&#xff1a;height [0,1,0,2,1,0,1,3,2,1,2,1] 输出&#xff1a;…...

golang 归并回源策略

前言 下面是我根据业务需求画了一个架构图&#xff0c;没有特别之处&#xff0c;很普通&#xff0c;都是我们常见的中间件&#xff0c;都是一些幂等性GET 请求。有一个地方很有意思&#xff0c;从service 分别有10000 qps 请求到Redis&#xff0c;并且它们的key 是一样的。这样…...

【漏洞复现】可视化融合指挥调度平台 dispatch接口处存在任意文件上传漏洞

免责声明&#xff1a;文章来源互联网收集整理&#xff0c;请勿利用文章内的相关技术从事非法测试&#xff0c;由于传播、利用此文所提供的信息或者工具而造成的任何直接或者间接的后果及损失&#xff0c;均由使用者本人负责&#xff0c;所产生的一切不良后果与文章作者无关。该…...

最讨厌这种字符串问题了!!

题目&#xff1a;洛谷P1957口算练习题 题目大意描述&#xff1a; 第一行输入一个整数表示接下来要进行多少次运算&#xff0c;接下来每行输入一个字母c和两个数字x,y&#xff08;输入的字母为a/b/c,分别表示要进行&#xff0c;-&#xff0c;*运算&#xff09;或者就输入两个数…...

B-名牌赌王(本人遇到的题,做个笔记)

题解&#xff1a; #include <iostream> #include <queue> //需要用小根堆的优先队列 #include <unordered_map> //用无序映射 using namespace std; bool pai() {int n, m;cin >> n >> m; priority_queue<int, vector<int>, gr…...

博客评论回复03

接着之前写的&#xff0c;之前返回的数据集按道理来说渲染出来还是丑丑的&#xff0c;因此这次我看着抖音的评论样子&#xff0c;自己瞎写了一通&#xff0c;不过也算是模仿出来了虽然肯定没有抖音写的好。 类似与前面几章写的表结构 首先看看抖音评论区是怎么样的&#xff1f…...

【【萌新的学习之Numpy数组的使用】】

萌新的学习之Numpy数组的使用 先记录一下之前的关于函数的设计 通过创造类的形式 复习完毕之后介绍numpy数组的使用 #整数型数组遇到除法 &#xff08;即便是除以整数&#xff09; 不同维度的数组之间 从外形上的本质区别 一维数组用1层中括号 二维数组用2层中括号 三维数…...

RabbitMQ3.13.x之七_RabbitMQ消息队列模型

RabbitMQ3.13.x之七_RabbitMQ消息队列模型 文章目录 RabbitMQ3.13.x之七_RabbitMQ消息队列模型1. RabbitMQ消息队列模型1. 简单队列2. Work Queues(工作队列)3. Publish/Subscribe(发布/订阅)4. Routing(路由)5. Topics(主题)6. RPC(远程过程调用)7. Publisher Confirms(发布者…...

Android JNI 调用第三方SO

最近一个项目使用了Go 编译了一个so库&#xff0c;但是这个so里面还需要使用第三方so库pdfium, 首先在Android工程把2个so库都放好 在jni中只能使用dlopen方式&#xff0c;其他的使用函数指针的方式来调用&#xff0c;和windows dll类似&#xff0c;不然虽然编译过了但是会崩溃…...

MVC 数据库

MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...

NLP学习路线图(二十三):长短期记忆网络(LSTM)

在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...

MySQL JOIN 表过多的优化思路

当 MySQL 查询涉及大量表 JOIN 时&#xff0c;性能会显著下降。以下是优化思路和简易实现方法&#xff1a; 一、核心优化思路 减少 JOIN 数量 数据冗余&#xff1a;添加必要的冗余字段&#xff08;如订单表直接存储用户名&#xff09;合并表&#xff1a;将频繁关联的小表合并成…...

Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、Spring MVC与MyBatis技术解析 一、第一轮基础概念问题 1. Spring框架的核心容器是什么&#xff1f;它的作用是什么&#xff1f; Spring框架的核心容器是IoC&#xff08;控制反转&#xff09;容器。它的主要作用是管理对…...

在Zenodo下载文件 用到googlecolab googledrive

方法&#xff1a;Figshare/Zenodo上的数据/文件下载不下来&#xff1f;尝试利用Google Colab &#xff1a;https://zhuanlan.zhihu.com/p/1898503078782674027 参考&#xff1a; 通过Colab&谷歌云下载Figshare数据&#xff0c;超级实用&#xff01;&#xff01;&#xff0…...

【Java多线程从青铜到王者】单例设计模式(八)

wait和sleep的区别 我们的wait也是提供了一个还有超时时间的版本&#xff0c;sleep也是可以指定时间的&#xff0c;也就是说时间一到就会解除阻塞&#xff0c;继续执行 wait和sleep都能被提前唤醒(虽然时间还没有到也可以提前唤醒)&#xff0c;wait能被notify提前唤醒&#xf…...

CSS 工具对比:UnoCSS vs Tailwind CSS,谁是你的菜?

在现代前端开发中&#xff0c;Utility-First (功能优先) CSS 框架已经成为主流。其中&#xff0c;Tailwind CSS 无疑是市场的领导者和标杆。然而&#xff0c;一个名为 UnoCSS 的新星正以其惊人的性能和极致的灵活性迅速崛起。 这篇文章将深入探讨这两款工具的核心理念、技术差…...

Netty自定义协议解析

目录 自定义协议设计 实现消息解码器 实现消息编码器 自定义消息对象 配置ChannelPipeline Netty提供了强大的编解码器抽象基类,这些基类能够帮助开发者快速实现自定义协议的解析。 自定义协议设计 在实现自定义协议解析之前,需要明确协议的具体格式。例如,一个简单的…...