#P1268. 【挑战题】MP3
【挑战题】MP3
题目描述
有一种数字化一段录音的常用方式,是记录每一个时刻的强度值。这些非负的强度值就可以代表一段音频
对于一段音频,若有 个不同的强度值,那么每一位我们都需要 来存储
也就是说,为了存储这一段音频,我们需要 个
为了压缩音频大小,我们们采取如下的方式:
选择两个整数 ,对于音频的强度值序列 ,将其作一次变换:
其中第 种情况被视作 这个强度值被更改了
你的任务是对于给定的强度值序列 ,找到一组 ,使得在经过上述压缩后能够被大小为 的存储器装下,并最小化被更改的强度值的数量
输入输出格式
输入格式
第一行包含两个正整数 ,描述了音量总时刻数与存储器大小
第二行包含 个正整数
对于第 个数,描述了 ( ),即时刻 的音量强度值
输出格式
输出答案,即在所有的适合存储器大小的压缩方案中,最小的被更改的强度值的数量
样例 #1
样例输入 #1
6 1
2 1 2 3 4 3
样例输出 #1
2
样例 #2
样例输入 #2
6 2
2 1 2 3 4 3
样例输出 #2
0
样例 #3
样例输入 #3
6 1
1 1 2 2 3 3
样例输出 #3
2
提示
在第一个例子中,我们可以选择 。数组变为 2 2 2 3 3 3,不同元素的数量为 ,只有两个值被改变。
在第二个例子中,不需要进行任何更改。
在第三个例子中,我们必须改变两个 1 或两个 3。