#P2273. [HNOI2002] 交换
[HNOI2002] 交换
题目描述
给定 个整数寄存器 。我们定义一个比较交换指令 如下:如果 中的值大于 中的值,则交换寄存器 和 中的值。其中,。
一个比较交换程序(简称为 CE-程序)就是一个有限交换指令序列。称一个 CE-程序为 MIN-程序,如果在该程序执行之后,寄存器 中的值是所有寄存器中的值的最小者;如果一个 CE-程序在删除其中任意一条交换指令后,仍然是一个 MIN-程序,则称该 CE-程序是可靠的 MIN-程序。
你的任务是:给定一个 CE-程序 P,编程求出至少在程序 P 的尾部增加多少条指令才能使程序 P 成为可靠的 MIN-程序。
例如,考虑下列三个寄存器的 CE-程序:
,,。
我们仅需要增加两条指令:, 就可使该 CE-程序成为可靠的 MIN-程序。
输入格式
共两行,第一行为用空格分开的两个整数 ;其中 为寄存器个数(), 为 CE-程序的指令条数()。
接下来为 条指令 , 之间用逗号分隔,两条指令之间也用逗号分隔。
输出格式
共一行一个整数即应该增加的最少指令条数。
3 3
1,2,2,3,1,2
2