{"trustable":false,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"声音数字化的一种常见方法是记录声音强度。每个时刻的强度都是一个非负整数,这样,我们可以将声音文件表示为有n个非负整数的数组。\u003cbr/\u003e\u003cbr/\u003e\n\n如果数组中元素的不同取值有K个,那么我们需要k\u003d⌈log\u003csub\u003e2\u003c/sub\u003eK⌉位来存储每一个值。因此,需要n*k位来存储整个文件。\u003cbr/\u003e\u003cbr/\u003e\n\n为了减少内存消耗,我们需要进行一些压缩。一种常见的方法是减少可能的强度值的数量。我们选择两个整数l≤r,然后按照以下方式更改所有强度值:如果强度值在[l,r]范围内,则不进行更改;如果小于l,我们将其更改为l;否则,如果它大于r,我们将其更改为r。您会看到我们损失了一些低强度和高强度。\u003cbr/\u003e\u003cbr/\u003e\n\n您的任务是应用这种压缩方式,使文件适合大小为M字节的磁盘,并且数组中已更改元素的数量尽可能少。\u003cbr/\u003e\u003cbr/\u003e\n\n我们提醒您1个字节包含8位。\u003cbr/\u003e\u003cbr/\u003e\n\nk =⌈log\u003csub\u003e2\u003c/sub\u003eK⌉是使得K≤2\u003csup\u003ek\u003c/sup\u003e的最小整数。特别地,如果K = 1,则k = 0。\u003cbr/\u003e\u003cbr/\u003e"}},{"title":"Input","value":{"format":"HTML","content":"第一行有两个整数n和M(1\u003c\u003dn\u003c\u003d400000, 1\u003c\u003dM\u003c\u003d10\u003csup\u003e8\u003c/sup\u003e),分别表示数组的长度和磁盘大小。\u003cbr/\u003e\n接下来一行有n个非负整数,保证不超过10\u003csup\u003e9\u003c/sup\u003e,代表声音大小。\u003cbr/\u003e"}},{"title":"Output","value":{"format":"HTML","content":"输出一个整数,需要改变的最少的数量。"}},{"title":"Examples","value":{"format":"HTML","content":"\u003cdiv class\u003d\"sample-test\"\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e\n \u003cpre\u003e6 1\n2 1 2 3 4 3\n\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e\n \u003cpre\u003e2\n\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e\n \u003cpre\u003e6 2\n2 1 2 3 4 3\n\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e\n \u003cpre\u003e0\n\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e\n \u003cpre\u003e6 1\n1 1 2 2 3 3\n\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e\n \u003cpre\u003e2\n\u003c/pre\u003e\n \u003c/div\u003e\n\u003c/div\u003e"}},{"title":"Note","value":{"format":"HTML","content":"在第一个示例中,我们可以选择l \u003d 2,r \u003d 3。 数组变为2 2 2 3 3 3,不同元素的数量为K \u003d 2,并且声音文件足够放入磁盘。 仅更改两个值。\u003cbr/\u003e\u003cbr/\u003e\n\n在第二个示例中,磁盘更大,因此初始文件可以容纳该文件,并且不需要进行任何更改。\u003cbr/\u003e\u003cbr/\u003e\n\n在第三个示例中,我们必须更改两个1或是两个3。\u003cbr/\u003e\u003cbr/\u003e"}}]}