#T0011. 徐老师的高达摆放

0

徐老师的高达摆放

题目描述 徐老师最近很喜欢收藏高达,但是高达的系列之作过多,而机甲手办的种类更是多到数不胜数,有国产 的,有日产的,有动漫改的,有动画改的,有纯为了摆件而设计的。 财大气粗的徐老师一次性订购了 n 台机甲手办,并且将它们横着一排摆放在展示柜上 但是他发现由于种类参差不齐,导致手办虽然多,但是丑! 于是徐老师心生一计——那就拿掉一些吧! 为了方便描述,徐老师给这 n 台手办机甲的种类进行了编号,第 i 台机甲的的种类为 ai 而懒惰的徐老师认为,只要现在放在展示柜上的机甲手办里,任意两种种类的机甲台数之差不超过 m, 那么这就是一种他可以接受的摆放方案 现在徐老师想知道,他最少需要拿走多少台机甲? 输入格式 输入第一行包含两个整数 n, m 含义如题 输入第二行包含 n 个整数 ai,分别表示每台机甲的种类 输出格式 输出一个整数,表示徐老师最少需要拿走的机甲数量 数据范围 对于 30% 的数据,数组长度 n ≤ 1000, 1 ≤ ai ≤ 100 对于 80% 的数据,数组长度 n ≤ 1000, 1 ≤ ai ≤ 100000 对于 100% 的数据,数组长度 n ≤ 100000, ai 在 int 范围内 样例输入1 7 1 2 2 3 1 2 3 1 样例输出1 0 样例解释1 不需要拿走任何机甲,所有种类的机甲出现次数之差不超过 1 样例输入2 6 1 2 2 1 2 3 1 样例输出2 1 样例解释2 删掉种类为 3 的机甲 徐老师的旅游规划 文件读写 输入文件travel.in 输出文件travel.out