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

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 - 思维 + 二分

分析&#xff1a; 首先找到边的指向很容易&#xff0c;但是暴力是o(n2&#xff09;&#xff0c;超时&#xff0c;可以将给定的式子变形&#xff0c;au - av > bu - bv即au - bu > av - bv&#xff0c;可以将两个数组转变为一个数组中的任意两个值之间的关系&#xff0c;因…...

8月9日上课内容 nginx负载均衡

负载均衡工作当中用的很多的&#xff0c;也是面试会问的很重要的一个点 负载均衡&#xff1a;通过反向代理来实现&#xff08;nginx只有反向代理才能做负载均衡&#xff09; 正向代理的配置方法&#xff08;用的较少&#xff09; 反向代理的方式&#xff1a;四层代理与七层代…...

为何我们都应关心算法备案?

随着技术的日新月异&#xff0c;算法成为现代生活的核心组成部分&#xff0c;从社交媒体推荐、在线广告到智能交通管理&#xff0c;几乎无处不在。然而&#xff0c;如此普及的技术给我们带来了一个新的挑战&#xff1a;如何确保算法的透明度、公正性和道德性&#xff1f;答案可…...

[IDEA]使用idea比较两个jar包的差异

除了一些小工具外&#xff0c;idea自带了jar包比较的功能。 把需要比对的jar包放到任意目录下&#xff0c;然后选中两个需要比较的jar包&#xff0c;右键&#xff0c;选择Compare Archives&#xff0c;然后就可以比较了。 这次疏忽了&#xff0c;每次打包前需要commit界面看一下…...

HTML笔记(2)

列表标签 项目标识符&#xff08;项目符号&#xff09;一般是不需要的 代码演示 改变符号样式&#xff0c;type属性 表格标签 代码演示 练习案例 布局标签 div是块儿级标签&#xff0c;占一整行&#xff1b; span标签不会占一整行&#xff0c;它只占包裹内容的那块儿区域&a…...

前端大屏自适应缩放

简介 前端中大屏往往用于展示各种炫酷的界面和特效&#xff0c;因此特别受用好欢迎。 但是在开发过程中&#xff0c;常常也会出现各种问题&#xff0c;与一般的页面相比&#xff0c; 最让人头疼的是大屏的自适应问题。使用CSS中transform属性和js获取缩放比例方法 先简单写一下…...

【Express.js】全面鉴权

全面鉴权 这一节我们来介绍一下 Passport.js&#xff0c;这是一个强大的 NodeJS 的认证中间件 Passport.js 提供了多种认证方式&#xff0c;账号密码、OpenID、ApiKey、JWT、OAuth、三方登录等等。 使用 Passport.js 认证要配置三个部分&#xff1a; 认证策略中间件会话 接…...

了解华为(H3C)网络设备和OSI模型基本概念

目录 一&#xff0c;认识华为 1.华为发展史 2.华为网络设备介绍 3.VRP概述 二&#xff0c;OSI七层模型 1.七层模型详细表格 2.各层的作用 3.数据在各层之间的传递过程 4.OSI四层网络模型 一&#xff0c;认识华为 官网&#xff1a;https://www.huawei.com/cn/ 1.华为发…...

Web3到底是个啥?

Web3是近两年来科技领域最火热的概念之一&#xff0c;但是目前对于Web3的定义却仍然没有形成标准答案&#xff0c;相当多对于Web3的理解&#xff0c;都是建立在虚拟货币行业&#xff08;即俗称的“币圈”&#xff09;的逻辑基础之上的。 区块链服务网络&#xff08;BSN&#x…...

山东高校的专利申请人经常掉进的误区2

02、专利技术交底书只提供简单思路 一些高校科研人员在申请专利时&#xff0c;给专利代理人的技术交底书往往只给出了思路&#xff0c;或者技术方案不够详细&#xff0c;或者根本不会有实验验证过程和数据。 事实上&#xff0c;专利技术交底书的详尽程度将直接影响代理人对技…...

关于webpack的基本配置

文章目录 前言一、webpack基本配置1.配置拆分和merge2. 启动服务3、处理es6&#xff0c;配置babel4、处理样式5、处理图片 前言 为什么要有webpack构建和打包&#xff1f; 更好的模块化管理。webpack支持模块化规范&#xff1a;代码分割成独立模块&#xff0c;并管理模块之间…...

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高级玩法分享

大家好&#xff0c;我是csdn的博主&#xff1a;lqj_本人 这是我的个人博客主页&#xff1a; lqj_本人_python人工智能视觉&#xff08;opencv&#xff09;从入门到实战,前端,微信小程序-CSDN博客 最新的uniapp毕业设计专栏也放在下方了&#xff1a; https://blog.csdn.net/lbcy…...

在指定的 DSN 中,驱动程序和应用程序之间的体系结构不匹配

1.Cadence 17.2 配置CIS数据库报&#xff1a;ERROR(ORCIS-6245): Database Operation Failed 安装cadance17.2以上版本时&#xff0c;ERROR(ORCIS-6245): Database Operation Failed_收湾湾的博客-CSDN博客 原因是ODBC数据库没有配置&#xff0c;或者没有驱动&#xff0c; 驱…...

API接口 |产品经理一定要懂的技术知识

什么是接口❓ 要理解接口是什么&#xff0c;首先理解一下为什么要用接口&#xff1f; 两个独立的系统&#xff0c;它们的数据或程序是独立的&#xff0c;这就使得它们无法直接访问对方的数据库或程序&#xff08;两个独立的数据相当于两个独立的家庭&#xff0c;每个家庭肯定是…...

C++中访问存储在数组中的数据

C中访问存储在数组中的数据 要访问数组中的元素&#xff0c;可使用从零开始的索引。这些索引之所以被称为从零开始的&#xff0c;是因为数组中第一个元素的索引为零。因此&#xff0c;存储在数组 myNumbers 中的第一个整数值为 myNumbers[0]&#xff0c;第二个为 myNumbers[1]…...

【创建型设计模式】C#设计模式之原型模式

原型模式是一种创建型设计模式&#xff0c;它通过复制现有对象来创建新对象&#xff0c;而无需通过实例化的方式。它允许我们使用已经存在的对象作为蓝本&#xff0c;从而创建新的对象&#xff0c;这样可以避免重复初始化相似的对象&#xff0c;提高了对象的创建效率。 现在给…...

用C语言高效地打印杨辉三角

假设杨辉三角的通项公式为a(n)&#xff0c;则打印形式如下&#xff1a; 然而我们知道&#xff0c;它应该是这样的&#xff1a; 三角形两边的值都为1&#xff0c;且每个元素的值都为该元素正上方和其正上方前面的元素的值之和。 为了实现这个代码&#xff0c;我们需要知道每行首…...

TCP/IP四层模型对比OSI七层网络模型的区别是啥?数据传输过程原来是这样的

一、TCP/IP四层模型对比OSI七层模型 它们两个定义的一些功能和协议都是差不多的。TCP/IP四层协议模型比我们的七层少了三层&#xff0c;把我们的数据链路层和物理层放在一层里面了&#xff0c;叫做数据链路层&#xff08;网络接口层&#xff09;&#xff0c;对应网络协议也没有…...

接口测试实战,Jmeter正则提取响应数据-详细整理,一篇打通...

目录&#xff1a;导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09; 前言 在测试时&#xf…...

华为云AI开发平台ModelArts

华为云ModelArts&#xff1a;重塑AI开发流程的“智能引擎”与“创新加速器”&#xff01; 在人工智能浪潮席卷全球的2025年&#xff0c;企业拥抱AI的意愿空前高涨&#xff0c;但技术门槛高、流程复杂、资源投入巨大的现实&#xff0c;却让许多创新构想止步于实验室。数据科学家…...

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag...

设计模式和设计原则回顾

设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

label-studio的使用教程(导入本地路径)

文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...

工业安全零事故的智能守护者:一体化AI智能安防平台

前言&#xff1a; 通过AI视觉技术&#xff0c;为船厂提供全面的安全监控解决方案&#xff0c;涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面&#xff0c;能够实现对应负责人反馈机制&#xff0c;并最终实现数据的统计报表。提升船厂…...

Go 语言接口详解

Go 语言接口详解 核心概念 接口定义 在 Go 语言中&#xff0c;接口是一种抽象类型&#xff0c;它定义了一组方法的集合&#xff1a; // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的&#xff1a; // 矩形结构体…...

Spring AI 入门:Java 开发者的生成式 AI 实践之路

一、Spring AI 简介 在人工智能技术快速迭代的今天&#xff0c;Spring AI 作为 Spring 生态系统的新生力量&#xff0c;正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务&#xff08;如 OpenAI、Anthropic&#xff09;的无缝对接&…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)

本文把滑坡位移序列拆开、筛优质因子&#xff0c;再用 CNN-BiLSTM-Attention 来动态预测每个子序列&#xff0c;最后重构出总位移&#xff0c;预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵&#xff08;S…...

GC1808高性能24位立体声音频ADC芯片解析

1. 芯片概述 GC1808是一款24位立体声音频模数转换器&#xff08;ADC&#xff09;&#xff0c;支持8kHz~96kHz采样率&#xff0c;集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器&#xff0c;适用于高保真音频采集场景。 2. 核心特性 高精度&#xff1a;24位分辨率&#xff0c…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...