A1826 | 最接近神的人
来源NOI
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
破解了符文之语，小 FF 开启了通往地下的道路。当他走到最底层时，发现正前方有一扇巨石门，门上雕刻着一幅古代人进行某种活动的图案。而石门上方用古代文写着“神的殿堂”。小 FF 猜想里面应该就有王室的遗产了。但现在的问题是如何打开这扇门……。
仔细研究后，他发现门上的图案大概是说：古代人认为只有智者才是最容易接近神明的。而最聪明的人往往通过一种仪式选拔出来。仪式大概是指，即将隐退的智者为他的候选人写下一串无序的数字，并让他们进行一种操作，即交换序列中相邻的两个元素。而用最少的交换次数使原序列变成不下降序列的人即是下一任智者。
小 FF 发现门上同样有着 $n$ 个数字。于是他认为打开这扇门的秘诀就是找到让这个序列变成不下降序列所需要的最小次数。但小 FF 不会……只好又找到了你，并答应事成之后与你三七分……
仔细研究后，他发现门上的图案大概是说：古代人认为只有智者才是最容易接近神明的。而最聪明的人往往通过一种仪式选拔出来。仪式大概是指，即将隐退的智者为他的候选人写下一串无序的数字，并让他们进行一种操作，即交换序列中相邻的两个元素。而用最少的交换次数使原序列变成不下降序列的人即是下一任智者。
小 FF 发现门上同样有着 $n$ 个数字。于是他认为打开这扇门的秘诀就是找到让这个序列变成不下降序列所需要的最小次数。但小 FF 不会……只好又找到了你，并答应事成之后与你三七分……
输入格式
第一行为一个整数 $n$，表示序列长度。
第二行为 $n$ 个整数，表示序列中每个元素。
第二行为 $n$ 个整数，表示序列中每个元素。
输出格式
一个整数 $\mathit{ans}$，即最少操作次数。
输入输出样例
输入 #1
4 2 8 0 3
输出 #1
3
### 数据范围及约定
- 对于 $30\%$ 的数据 $1≤n≤10^4$。
- 对于 $100\%$ 的数据 $1≤n≤5\times 10^5$，$A_i\in [-2^{31}, 2^{31})$。
### 样例解释
开始序列为 $[2,8,0,3]$，目标序列为 $[0, 2, 3, 8]$，可进行三次操作的目标序列：
1. 交换 $(8,0)$，序列变成 $[2,0,8,3]$；
2. 交换 $(2,0)$，序列变成 $[0,2,8,3]$；
3. 交换 $(8,3)$，序列变成 $[0,2,3,8]$。
- 对于 $30\%$ 的数据 $1≤n≤10^4$。
- 对于 $100\%$ 的数据 $1≤n≤5\times 10^5$，$A_i\in [-2^{31}, 2^{31})$。
### 样例解释
开始序列为 $[2,8,0,3]$，目标序列为 $[0, 2, 3, 8]$，可进行三次操作的目标序列：
1. 交换 $(8,0)$，序列变成 $[2,0,8,3]$；
2. 交换 $(2,0)$，序列变成 $[0,2,8,3]$；
3. 交换 $(8,3)$，序列变成 $[0,2,3,8]$。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted