#P107. 数据修复(repair.cpp)
数据修复(repair.cpp)
cwbc曾经存有一个长度为n的整数序列 ,由于某次操作失误,导致序列中的部分数据丢失,例如原序列为 ,丢失数据后变为了
,其中 表示丢失的数据。
cwbc想要修复这组数据,但他只记得序列中的每个数字都是 之间的整数。于是,他打算找出一种修复方案,使得修复后序列中的逆序对对数尽量少。
####【输入格式】
第一行两个正整数 。
第二行 个整数,每个整数要么在 之间,要么为 ,表示数据丢失后的序列 。
####【输出格式】
一行,一个整数,表示最少的逆序对数。 ####【样例输入】
5 4
4 2 -1 -1 3
####【样例输出】
4
###【数据范围】
|测试点编号 |n<=| k<=| -1的数量不超过| | | | | | |1 | 6 | 5 | n| |2 | 100 | 100 | 1| |3 | 100 | 100 | 2| |4 | 100 | 100 | n| |5 | 100000 | 100 | 0| |6 | 100000 | 100 | 8| |7 | 100000 | 100 | 11| |8 | 2000 | 100 | n| |9 | 100000 | 100 | n | |10 | 100000 | 100 | n|