A3121 | 彩球排序
时间限制3s
内存限制512MB
通过 / 提交0/0
题目描述
时间限制：3000ms
内存限制：512MB
有 $N$ 个球从左到右排列。第 $i$ 个球的颜色是颜色 $C_i$，并且上面写有一个整数 $X_i$。
小码君想要对这些球排序，使得球上的整数从左到右是非递减的。
换句话说，他的目标是：对于任意 $i\ (1\leq i\leq N-1)$，从左数第 $(i+1)$ 个球上的数字大于或等于从左数第 $i$ 个球上的数字。
为此，小码君可以重复执行以下操作任意次（可能为零次）：
1. 选择一个整数 $i\ (1\leq i\leq N-1)$。
2. 如果从左数第 $i$ 个球和第 $(i+1)$ 个球的颜色不同，则支付 $1$ 元钱。 （如果颜色相同，则不需要支付费用）。
3. 交换从左数第 $i$ 个球和第 $(i+1)$ 个球的位置。
求小码君为了实现目标需要支付的最小总费用。
$\large{数据范围}$
- $2 \leq N \leq 3\times 10^5$
- $1\leq C_i\leq N$
- $1\leq X_i\leq N$
- 所有输入数据均为整数。
输入格式
对于每个测试文件格式如下：
$\tt{C_1\ C_2\ \ldots\ C_N}$
$\tt{X_1\ X_2\ \ldots\ X_N}$
$\tt{N}$
$\tt{C_1\ C_2\ \ldots\ C_N}$
$\tt{X_1\ X_2\ \ldots\ X_N}$
输出格式
对于每个测试文件输出为实现目标所需的最低总成本。
输入输出样例
输入 #1
5 1 5 2 2 1 3 2 1 2 1
输出 #1
6
输入 #2
3 1 1 1 3 2 1
输出 #2
0
输入 #3
3 3 1 2 1 1 2
输出 #3
0
样例 $1$：
我们使用 $($ 颜色 $,$ 整数 $)$ 的二元组来表示一个球。
球的初始顺序为 $(1,3)$，$(5,2)$，$(2,1)$，$(2,2)$，$(1,1)$。以下为操作步骤：
第 $1$、 $2$、 $3$、 $5$、 $6$ 和第 $7$ 次操作各产生 $1$ 元的费用，总花费为 $6$，即最小花费。
需要注意的是，第 $4$ 次操作不会产生费用，因为两个球的颜色都是 $1$ 。
样例 $2$：
所有球的颜色相同，因此交换球不产生任何费用。
样例 $3$：
所有球上的数字已经按照非递减顺序排列，无需任何操作。
我们使用 $($ 颜色 $,$ 整数 $)$ 的二元组来表示一个球。
球的初始顺序为 $(1,3)$，$(5,2)$，$(2,1)$，$(2,2)$，$(1,1)$。以下为操作步骤：
- 交换第 $1$ 个球（颜色 $1$）和第 $2$ 个球（颜色 $5$）。现在球的顺序是 $(5,2)$，$(1,3)$，$(2,1)$，$(2,2)$，$(1,1)$。
- 交换第 $2$ 个球（颜色 $1$）和第 $3$ 个球（颜色 $2$）。现在球的顺序是 $(5,2)$，$(2,1)$，$(1,3)$，$(2,2)$，$(1,1)$。
- 交换第 $3$ 个球（颜色 $1$）和第 $4$ 个球（颜色 $2$）。现在球的顺序是 $(5,2)$，$(2,1)$，$(2,2)$，$(1,3)$，$(1,1)$。
- 交换第 $4$ 个球（颜色 $1$）和第 $5$ 个球（颜色 $1$）。现在球的顺序是 $(5,2)$，$(2,1)$，$(2,2)$，$(1,1)$，$(1,3)$。
- 交换第 $3$ 个球（颜色 $2$）和第 $4$ 个球（颜色 $1$）。现在球的顺序是 $(5,2)$，$(2,1)$，$(1,1)$，$(2,2)$，$(1,3)$。
- 交换第 $1$ 个球（颜色 $5$）和第 $2$ 个球（颜色 $2$）。现在球的顺序是 $(2,1)$，$(5,2)$，$(1,1)$，$(2,2)$，$(1,3)$。
- 交换第 $2$ 个球（颜色 $5$）和第 $3$ 个球（颜色 $1$）。现在球的顺序是 $(2,1)$，$(1,1)$，$(5,2)$，$(2,2)$，$(1,3)$。
第 $1$、 $2$、 $3$、 $5$、 $6$ 和第 $7$ 次操作各产生 $1$ 元的费用，总花费为 $6$，即最小花费。
需要注意的是，第 $4$ 次操作不会产生费用，因为两个球的颜色都是 $1$ 。
样例 $2$：
所有球的颜色相同，因此交换球不产生任何费用。
样例 $3$：
所有球上的数字已经按照非递减顺序排列，无需任何操作。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？