罗勇军 → 《算法竞赛·快冲300题》每日一题:“排列变换” ← 贪心算法
【题目来源】
http://oj.ecustacm.cn/problem.php?id=1812
http://oj.ecustacm.cn/viewnews.php?id=1023
【题目描述】
给定一个长度为 n 的排列 a,需要将这个排列变成 b。
每次可以选择一个数字往左移若干个位置。
请求出最小需要移动的元素个数。
【输入格式】
第一行为正整数 n,1≤n≤100000。
第二行为 n 个整数,表示排列 a。
第三行为 n 个整数,表示排列 b。
【输出格式】
输出一个数字表示答案,即最小需要移动的元素个数。
【输入样例】
5
5 1 3 2 4
4 5 2 1 3
【输出样例】
2
【算法分析】
** 将原序列 a 重排为序列 b,则原序列 a 中各元素在序列 b 中的位置 p[] 可通过以下代码获得:
tp[b[i]]=i, p[i]=tp[a[i]]
** 分析位置序列 p[] 中每个数,如果当前的数比左边的数小就不断左移,否则不用移动。这是贪心算法的思路。
例如,针对样例中给出的原始序列 a[]=[5 1 3 2 4] 中的各元素,利用“tp[b[i]]=i, p[i]=tp[a[i]]”,可得出它们在重排序列 b[]=[4 5 2 1 3] 中的位置序列为 p[]=[2 4 5 3 1]。显然,通过观察位序的相对位置,可知需要移动两个数字。
【算法代码】
#include <bits/stdc++.h>
using namespace std;const int N=1e5+5;
int a[N],b[N];
int p[N]; //p[x]:subscript of number x in the b array
int tp[N];int main() {int n;cin>>n;for(int i=1; i<=n; i++) cin>>a[i];for(int i=1; i<=n; i++) {cin>>b[i];tp[b[i]]=i;}for(int i=1; i<=n; i++) p[i]=tp[a[i]];int ans=0;int t=0;for(int i=1; i<=n; i++) {if(t>p[i]) ans++;t=max(t,p[i]);}cout<<ans<<endl;return 0;
}/*
in:
5
5 1 3 2 4
4 5 2 1 3out:
2
*/
【参考文献】
https://blog.csdn.net/weixin_43914593/article/details/131741061
相关文章:
罗勇军 → 《算法竞赛·快冲300题》每日一题:“排列变换” ← 贪心算法
【题目来源】http://oj.ecustacm.cn/problem.php?id1812http://oj.ecustacm.cn/viewnews.php?id1023【题目描述】 给定一个长度为 n 的排列 a,需要将这个排列变成 b。 每次可以选择一个数字往左移若干个位置。 请求出最小需要移动的元素个数。【输入格式】 第一行…...
算法修炼Day51|● 309.最佳买卖股票时机含冷冻期 ● 714.买卖股票的最佳时机含手续费
LeetCode:309.最佳买卖股票时机含冷冻期 309. 买卖股票的最佳时机含冷冻期 - 力扣(LeetCode) 1.思路 初始化dp[i][j]数组,表示第i天的最大利润为dp[i][j]. 精确的定义状态是个难点,可以定义四种状态:持有股票&#…...
LVS-DR模型实例
一、LVS-DR集群介绍 LVS-DR(Linux Virtual Server Director Server)工作模式,是生产环境中最常用的一 种工作模式。 1、LVS-DR 工作原理 LVS-DR 模式,Director Server 作为群集的访问入口,不作为网关使用࿰…...
Vue面试题
1. vue优点 轻量级速度快简单易学低耦合可重用性独立开发文档齐全,且文档为中文文档 2. ## vue中组件间传值 prop/$emit 父子组件传值 ref 和 $parent/$children 父子组件传值 eventBus($emit/$on) 父子,隔代,兄弟组件传值 $attrs/$listeners…...
使用图像处理算法检测金属表面的生锈区域: Python实现及步骤解析
摘要: 本文主要介绍如何使用Python和OpenCV库来实现对金属表面的生锈区域的检测。图像处理在工业领域有着广泛的应用,尤其是对材料的表面缺陷的检测。本文将详细阐述该算法的具体实现步骤,并提供完整的Python代码示例。 1. 引言 金属的锈蚀是…...
通过爬虫抓取上市企业利润表并在睿思BI中展示
睿思BI从v5.3开始支持网络爬虫,可以从指定URL抓取表格数据,本示例实现从网络上抓取上市企业招商银行的利润表数据,并在睿思BI中进行展现。 功能演示URL:https://www.ruisitech.com/rsbi-ultimate/#/dashboard/ShareView?token31…...
填充柄功能
单元格右下角十字符号 顺序式填充 输入1,2,直接拉取即可实现顺序1到10. 复制式填充 CtrlD或者拉取,选择右下角复制单元格。 规律式填充 输入星期一,星期二,下拉一直可以到星期日 自定义填充 选择文件-》选项-》自定义序列 输…...
Python爬虫性能优化:多进程协程提速实践指南
目录 1. 多进程爬虫的实现: 1.1 将爬虫任务划分成多个子任务: 1.2 创建进程池: 1.3 执行任务: 1.4 处理结果: 代码示例 2. 协程爬虫的实现: 2.1 定义异步爬虫函数: 2.2 创建事件循环&a…...
mongodb export(2023新)
之前的mongodb export发现不能用了,T3带ui的版本,试用到期不支持导出。 根据文档,是因为server版本更新后 tool版本没有升级,(refs文档) 按文档下载bin,后解压到更新本地文件夹,替换/usr/local/bin里的文…...
css-flex使用
文章目录 flex弹性容器属性flex-directionflex-wrapflex-flowalign-itemsjustify-contentalign-content主轴和侧轴 弹性元素默认大小属性flex-growflex-shrinkalign-selfflex-basisflexorder 高度坍塌flex布局子元素宽度超出父元素 flex 弹性盒,伸缩盒,…...
SAP安全库存-安全库存共享、安全库存简介
SAP系统中的安全库存用于管理计划外和计划内的库存需求,在某些行业中,由于不同的情况,如意外损耗、损坏、环境问题、制造工艺问题、需求增加等,通常会出现意外的库存需求。 SAP提供了维护安全库存的处理方式来处理这样的问题,安全库存的字段信息在主数据视图中,在物料需…...
CentOS自己搭建时钟同步服务实操
目录 1、产生背景 2、操作过程 3、客户端操作 4、ntpd和ntpdate的区别 5、参考文章 1、产生背景 因为公司业务,需要使用一些网关设备上报监测实时数据,为了保障数据时钟一致性,所以需要提供一天时钟校验服务器。因为原来这个厂家的网关设…...
高阶数据结构-图
高阶数据结构-图 图的表示 图由顶点和边构成,可分为有向图和无向图 邻接表法 图的表示方法有邻接表法和邻接矩阵法,以上图中的有向图为例,邻接表法可以表示为 A->[(B,5),(C,10)] B->[(D,100)] C->[(B,3)] D->[(E,7)] E->[…...
Linux/Ubuntu 的日常升级和安全更新,如何操作?
我安装的是Ubuntu 20.04.6 LTS的Windows上Linux子系统版本,启动完成后显示: Welcome to Ubuntu 20.04.6 LTS (GNU/Linux 5.15.90.4-microsoft-standard-WSL2 x86_64) * Documentation: https://help.ubuntu.com * Management: https://landscape.c…...
Linux自动挂载U盘
文章目录 UEDV规则文件挂在U盘规则,创建.ruiles将下放代码放入 UEDV规则文件 规则文件是 udev 里最重要的部分,默认是存放在 /etc/udev/rule.d/ 下。所有的规则文件必须以".rules" 为后缀名。 下面是一个简单的规则: KERNEL"…...
Edge浏览器免费使用GPT3.5
搜索sider,安装Sidebar插件 注册账号即可每天免费使用30次。 Sider: ChatGPT侧边栏,GPT-4, 联网, 绘图...
面试题--redis篇
一、Redis支持的数据类型? String (字符串) Hash (哈希) List (列表) Set (集合) zset (sorted set:有序集合) 1. String(字符串) 格式: set key value string 类型是二进制安全的,意思是 redis 的 string 可以包含任…...
Android Studio 新建module报错:No signature of method
android平台uni原生插件开发过程中,使用Android Studio 新增 module 报错 选择app --> create new module ,填写相关信息 Android Studio 新建module报错: 原因:Android Studio 版本过高,新增了namespace&#x…...
python使用dir()函数获取对象中可用的属性和方法(看不到python源码又想知道怎么调用,DLL调用分析,SDK二次开发技巧)
有时候调用一些SDK,但是人家又是封装成dll文件形式调用的,这时没法看源码,也不想看其对应的开发文档(尤其有些开发文档写得还很难懂,或者你从某个开源社区拿过来,就根本没找到开发文档)…...
【MySQL系列】SQL语句入门(创建删除操作)、字符集和数据类型详解
💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤 📃个人主页 :阿然成长日记 …...
观成科技:隐蔽隧道工具Ligolo-ng加密流量分析
1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具,该工具基于TUN接口实现其功能,利用反向TCP/TLS连接建立一条隐蔽的通信信道,支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式,适应复杂网…...
相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了: 这一篇我们开始讲: 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下: 一、场景操作步骤 操作步…...
渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止
<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet: https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...
cf2117E
原题链接:https://codeforces.com/contest/2117/problem/E 题目背景: 给定两个数组a,b,可以执行多次以下操作:选择 i (1 < i < n - 1),并设置 或,也可以在执行上述操作前执行一次删除任意 和 。求…...
爬虫基础学习day2
# 爬虫设计领域 工商:企查查、天眼查短视频:抖音、快手、西瓜 ---> 飞瓜电商:京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空:抓取所有航空公司价格 ---> 去哪儿自媒体:采集自媒体数据进…...
Device Mapper 机制
Device Mapper 机制详解 Device Mapper(简称 DM)是 Linux 内核中的一套通用块设备映射框架,为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程,并配以详细的…...
【Go语言基础【12】】指针:声明、取地址、解引用
文章目录 零、概述:指针 vs. 引用(类比其他语言)一、指针基础概念二、指针声明与初始化三、指针操作符1. &:取地址(拿到内存地址)2. *:解引用(拿到值) 四、空指针&am…...
处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的
修改bug思路: 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑:async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...
RSS 2025|从说明书学习复杂机器人操作任务:NUS邵林团队提出全新机器人装配技能学习框架Manual2Skill
视觉语言模型(Vision-Language Models, VLMs),为真实环境中的机器人操作任务提供了极具潜力的解决方案。 尽管 VLMs 取得了显著进展,机器人仍难以胜任复杂的长时程任务(如家具装配),主要受限于人…...
【SpringBoot自动化部署】
SpringBoot自动化部署方法 使用Jenkins进行持续集成与部署 Jenkins是最常用的自动化部署工具之一,能够实现代码拉取、构建、测试和部署的全流程自动化。 配置Jenkins任务时,需要添加Git仓库地址和凭证,设置构建触发器(如GitHub…...
