问题 T: [深入浅出学算法][排序专题] 排序大师的存储大业
时间限制: 1 Sec 内存限制: 128 MB
提交: 50 解决: 2
[提交] [状态] [讨论版] [命题人:tpengshuhai]
题目描述
排序大师最近在研究如何存储视频（可以理解为是n个数字），他研究出一种方法：对于n个数，它所需要的内存空间为⌈log2K⌉*n，其中K=数组中数字的种类数。为了减少内存的使用，通过选择两个整数L<=R，对于数组中小于L的数字，都变为L；大于R的数字都变为R。
电脑存储空间为8*I，请问至少需要改变几个数字(改变K)才能使得能够存储视频
输入
第一行输入一个整数N(1<=N<=100000)，一个整数I(I<=I<=100000)
第二行输入N个整数ai(0<=a[i]<=10^9)
输出
从小到大输出N个数，每相邻两个数之间有一个空格
样例输入
6 1
2 1 2 3 4 3
样例输出
2
提示
在样例中，我们选择l = 2，r = 3。 数组变为2 2 2 3 3 3，不同元素的数量为K = 2。
所需要的存储空间为6 <= 1*8（内存空间）
