Codeforces 1199C – MP3

题目链接:Codeforces 1199C

统计每个数字出现的个数,考虑贪心地去最大的$K$,删掉最少的数。对于$k = \lceil \log_2 K \rceil$固定的时候,取$k =  \log_2 K $即$K = 2 ^ k$最大。而从$n k \leq 8I$可以看出$k_{\max} = \lfloor \frac{8I}{n} \rfloor$,因此我们可以求出最多可以保留多少种数(注意$K$小于等于种类总数)和最少删掉多少种数,枚举前面删几个后面删几个即可,预处理前缀和。

坑点:1<<k会爆int,应当使用1LL<<k

 

说点什么

avatar
50
  Subscribe  
提醒