#P001P1088. 邪恶的集合(加强版)
邪恶的集合(加强版)
题目描述
在一片邪恶之地,邪恶博士绑架了Mahmoud和Ehab,因为他们在邪恶信息学奥林匹克竞赛(Evil Olympiad in Informatics,EOI)中的突出表现。邪恶博士又决定给他们一些问题让他们回答。问题如下:
邪恶博士对集合很感兴趣。他有一个包含n个整数的集合。邪恶博士认为,如果一个集合的Mex值恰好为x,那么这个集合就是邪恶的。定义Mex值为一个集合中没有出现的最小非负整数。举个例子,Mex({0,2,4}) = 1(集合中没出现过的最小非负整数是1。),Mex({1,2,3}) = 0 (集合中没出现过的最小非负整数是0。)。
邪恶博士想让他的集合变得邪恶,因此他会执行一些操作。在每个操作中他可能会加入一个非负整数,也可能删去一个数。请问最少需要多少次操作才能让邪恶博士的集合变得邪恶?
输入格式:
第一行,包括两个整数n和x,意义如上述。
第二行,包括n个不同的非负整数,且每个数均不超过,表示一开始集合中的元素。
输出格式:
仅输出一行,表示邪恶博士最少需要执行多少次操作。
数据范围
50% 数据: 。
100%数据:
Samples
5 3
0 4 5 6 7
2
1 0
0
1
5 0
1 2 3 4 5
0
Note
对于第一个测试用例,Dr. Evil 应该将 1 和 2 添加到集合中,使3变成最小非负整数。执行 2 次操作。
对于第二个测试用例,Dr. Evil 应该从集合中删除 0。之后,集合变为空,因此它的 MEX 为 0。
在第三个测试用例中,集合已经是邪恶的。