D. Strong Vertices - 思维 + 二分



分析:
首先找到边的指向很容易,但是暴力是o(n2),超时,可以将给定的式子变形,au - av >= bu - bv即au - bu >= av - bv,可以将两个数组转变为一个数组中的任意两个值之间的关系,因此可以遍历整个数组,在其中二分查找每一个符合条件的数,就可以优化时间复杂度。
代码:
#include <bits/stdc++.h>using namespace std;
using ll = long long;typedef pair<ll,int> pii;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int T;cin >> T;while(T --) {int n;cin >> n;vector<pii> a(n);vector<ll> b(n);for(int i=0;i<n;i++) cin>>a[i].first;for(int i=0;i<n;i++) cin>>b[i];vector<int> x(n+1);for(int i=0;i<n;i++) {a[i].first-=b[i];a[i].second = i+1;}// for(int i=0;i<a.size();i++) cout<<a[i].first<<' ';// cout<<endl;sort(a.begin(),a.end());//for(int i=0;i<a.size();i++) cout<<a[i].first<<' ';// cout<<endl;for(int i=0;i<a.size();i++) {int l=0;int r=a.size()-1;while(l<r) {int mid=(l+r+1)/2;if(a[mid].first<=a[i].first) l=mid;else r=mid-1;}x[a[i].second]=l;// cout<<a[i].second << ' ' <<l<<endl;}vector<int> ans;for(int i=1;i<=n;i++) {// cout<<x[i]<<' ';if(x[i]==n-1) ans.push_back(i);}cout<<ans.size()<<'\n';for(int i=0;i<ans.size();i++) cout<<ans[i]<<' ';cout<<'\n';}
}
相关文章:
D. Strong Vertices - 思维 + 二分
分析: 首先找到边的指向很容易,但是暴力是o(n2),超时,可以将给定的式子变形,au - av > bu - bv即au - bu > av - bv,可以将两个数组转变为一个数组中的任意两个值之间的关系,因…...
8月9日上课内容 nginx负载均衡
负载均衡工作当中用的很多的,也是面试会问的很重要的一个点 负载均衡:通过反向代理来实现(nginx只有反向代理才能做负载均衡) 正向代理的配置方法(用的较少) 反向代理的方式:四层代理与七层代…...
为何我们都应关心算法备案?
随着技术的日新月异,算法成为现代生活的核心组成部分,从社交媒体推荐、在线广告到智能交通管理,几乎无处不在。然而,如此普及的技术给我们带来了一个新的挑战:如何确保算法的透明度、公正性和道德性?答案可…...
[IDEA]使用idea比较两个jar包的差异
除了一些小工具外,idea自带了jar包比较的功能。 把需要比对的jar包放到任意目录下,然后选中两个需要比较的jar包,右键,选择Compare Archives,然后就可以比较了。 这次疏忽了,每次打包前需要commit界面看一下…...
HTML笔记(2)
列表标签 项目标识符(项目符号)一般是不需要的 代码演示 改变符号样式,type属性 表格标签 代码演示 练习案例 布局标签 div是块儿级标签,占一整行; span标签不会占一整行,它只占包裹内容的那块儿区域&a…...
前端大屏自适应缩放
简介 前端中大屏往往用于展示各种炫酷的界面和特效,因此特别受用好欢迎。 但是在开发过程中,常常也会出现各种问题,与一般的页面相比, 最让人头疼的是大屏的自适应问题。使用CSS中transform属性和js获取缩放比例方法 先简单写一下…...
【Express.js】全面鉴权
全面鉴权 这一节我们来介绍一下 Passport.js,这是一个强大的 NodeJS 的认证中间件 Passport.js 提供了多种认证方式,账号密码、OpenID、ApiKey、JWT、OAuth、三方登录等等。 使用 Passport.js 认证要配置三个部分: 认证策略中间件会话 接…...
了解华为(H3C)网络设备和OSI模型基本概念
目录 一,认识华为 1.华为发展史 2.华为网络设备介绍 3.VRP概述 二,OSI七层模型 1.七层模型详细表格 2.各层的作用 3.数据在各层之间的传递过程 4.OSI四层网络模型 一,认识华为 官网:https://www.huawei.com/cn/ 1.华为发…...
Web3到底是个啥?
Web3是近两年来科技领域最火热的概念之一,但是目前对于Web3的定义却仍然没有形成标准答案,相当多对于Web3的理解,都是建立在虚拟货币行业(即俗称的“币圈”)的逻辑基础之上的。 区块链服务网络(BSN&#x…...
山东高校的专利申请人经常掉进的误区2
02、专利技术交底书只提供简单思路 一些高校科研人员在申请专利时,给专利代理人的技术交底书往往只给出了思路,或者技术方案不够详细,或者根本不会有实验验证过程和数据。 事实上,专利技术交底书的详尽程度将直接影响代理人对技…...
关于webpack的基本配置
文章目录 前言一、webpack基本配置1.配置拆分和merge2. 启动服务3、处理es6,配置babel4、处理样式5、处理图片 前言 为什么要有webpack构建和打包? 更好的模块化管理。webpack支持模块化规范:代码分割成独立模块,并管理模块之间…...
SpringBoot WebSocket配合react 使用消息通信
引入websocket依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-websocket</artifactId></dependency>配置websocket import org.springframework.context.annotation.Bean; import org.spr…...
【积水成渊】uniapp高级玩法分享
大家好,我是csdn的博主:lqj_本人 这是我的个人博客主页: lqj_本人_python人工智能视觉(opencv)从入门到实战,前端,微信小程序-CSDN博客 最新的uniapp毕业设计专栏也放在下方了: https://blog.csdn.net/lbcy…...
在指定的 DSN 中,驱动程序和应用程序之间的体系结构不匹配
1.Cadence 17.2 配置CIS数据库报:ERROR(ORCIS-6245): Database Operation Failed 安装cadance17.2以上版本时,ERROR(ORCIS-6245): Database Operation Failed_收湾湾的博客-CSDN博客 原因是ODBC数据库没有配置,或者没有驱动, 驱…...
API接口 |产品经理一定要懂的技术知识
什么是接口❓ 要理解接口是什么,首先理解一下为什么要用接口? 两个独立的系统,它们的数据或程序是独立的,这就使得它们无法直接访问对方的数据库或程序(两个独立的数据相当于两个独立的家庭,每个家庭肯定是…...
C++中访问存储在数组中的数据
C中访问存储在数组中的数据 要访问数组中的元素,可使用从零开始的索引。这些索引之所以被称为从零开始的,是因为数组中第一个元素的索引为零。因此,存储在数组 myNumbers 中的第一个整数值为 myNumbers[0],第二个为 myNumbers[1]…...
【创建型设计模式】C#设计模式之原型模式
原型模式是一种创建型设计模式,它通过复制现有对象来创建新对象,而无需通过实例化的方式。它允许我们使用已经存在的对象作为蓝本,从而创建新的对象,这样可以避免重复初始化相似的对象,提高了对象的创建效率。 现在给…...
用C语言高效地打印杨辉三角
假设杨辉三角的通项公式为a(n),则打印形式如下: 然而我们知道,它应该是这样的: 三角形两边的值都为1,且每个元素的值都为该元素正上方和其正上方前面的元素的值之和。 为了实现这个代码,我们需要知道每行首…...
TCP/IP四层模型对比OSI七层网络模型的区别是啥?数据传输过程原来是这样的
一、TCP/IP四层模型对比OSI七层模型 它们两个定义的一些功能和协议都是差不多的。TCP/IP四层协议模型比我们的七层少了三层,把我们的数据链路层和物理层放在一层里面了,叫做数据链路层(网络接口层),对应网络协议也没有…...
接口测试实战,Jmeter正则提取响应数据-详细整理,一篇打通...
目录:导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结(尾部小惊喜) 前言 在测试时…...
IDEA运行Tomcat出现乱码问题解决汇总
最近正值期末周,有很多同学在写期末Java web作业时,运行tomcat出现乱码问题,经过多次解决与研究,我做了如下整理: 原因: IDEA本身编码与tomcat的编码与Windows编码不同导致,Windows 系统控制台…...
vscode里如何用git
打开vs终端执行如下: 1 初始化 Git 仓库(如果尚未初始化) git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...
Java 语言特性(面试系列1)
一、面向对象编程 1. 封装(Encapsulation) 定义:将数据(属性)和操作数据的方法绑定在一起,通过访问控制符(private、protected、public)隐藏内部实现细节。示例: public …...
LeetCode - 394. 字符串解码
题目 394. 字符串解码 - 力扣(LeetCode) 思路 使用两个栈:一个存储重复次数,一个存储字符串 遍历输入字符串: 数字处理:遇到数字时,累积计算重复次数左括号处理:保存当前状态&a…...
将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?
Otsu 是一种自动阈值化方法,用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理,能够自动确定一个阈值,将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...
spring:实例工厂方法获取bean
spring处理使用静态工厂方法获取bean实例,也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下: 定义实例工厂类(Java代码),定义实例工厂(xml),定义调用实例工厂ÿ…...
在Ubuntu中设置开机自动运行(sudo)指令的指南
在Ubuntu系统中,有时需要在系统启动时自动执行某些命令,特别是需要 sudo权限的指令。为了实现这一功能,可以使用多种方法,包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法,并提供…...
RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程
本文较长,建议点赞收藏,以免遗失。更多AI大模型应用开发学习视频及资料,尽在聚客AI学院。 本文全面剖析RNN核心原理,深入讲解梯度消失/爆炸问题,并通过LSTM/GRU结构实现解决方案,提供时间序列预测和文本生成…...
深度学习习题2
1.如果增加神经网络的宽度,精确度会增加到一个特定阈值后,便开始降低。造成这一现象的可能原因是什么? A、即使增加卷积核的数量,只有少部分的核会被用作预测 B、当卷积核数量增加时,神经网络的预测能力会降低 C、当卷…...
MFC 抛体运动模拟:常见问题解决与界面美化
在 MFC 中开发抛体运动模拟程序时,我们常遇到 轨迹残留、无效刷新、视觉单调、物理逻辑瑕疵 等问题。本文将针对这些痛点,详细解析原因并提供解决方案,同时兼顾界面美化,让模拟效果更专业、更高效。 问题一:历史轨迹与小球残影残留 现象 小球运动后,历史位置的 “残影”…...
