题解归档 - cf1198A

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf1198A
• 本地来源：problems/cf1198A/idea.md
• 题目链接：https://codeforces.com/contest/1198/problem/A
• 原始标题：CF1198A — MP3

思路

CF1198A — MP3

题意

给定长度 n 的整数数组，选 l ≤ r，把 < l 的改成 l、把 > r 的改成 r。压缩后不同值个数为 K，每个值需 k = ⌈log₂ K⌉ 位，总位数 nk 不能超过 I 字节（8I 位）。求最少修改元素个数。

关键观察

1. 排序后，最优 l、r 一定取排序数组中某段连续下标 [i, j] 对应的 a[i] 与 a[j]：保留区间内原值，左侧全压到 l=a[i]，右侧全压到 r=a[j]。
2. 压到 l/r 不会产生新的不同值（l、r 已在区间内出现）。
3. 修改数 = (i-1) + (n-j)（1-based）。
4. 约束：n · ⌈log₂ K⌉ ≤ 8I，其中 K 为区间 [i,j] 内不同值个数。

算法

双指针滑动窗口：

• 维护窗口 [i, j] 的不同值个数 zc。
• 对每个左端 i，尽量右扩 j；若 n·kbit(zc) > 8I 则停止扩张。
• 在合法窗口上更新 ans = min(ans, i-1+n-j)。
• kbit(K) 用 K≤1 → 0，否则 64-__builtin_clzll(K-1) 即 ⌈log₂ K⌉。

复杂度 O(n log n) 排序 + O(n) 双指针。

验证

• 样例通过。
• Kali 本地对拍 500 组（gen + brute vs solution）全部一致。

结论

经典双指针 + 不同值计数；Div.1 A 题。

代码

来源：problems/cf1198A/solution.cpp

/* Author: likely
 * Time: 2026-06-08 03:16:28
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=4e5+5;
ll s[maxn],n,I,i,j,ans,zc;
map<ll,ll>mp;
ll kbit(ll K){
    if(K<=1) return 0;
    return 64-__builtin_clzll(K-1);
}
int main(){
    cin>>n>>I;
    for(i=1;i<=n;i++) cin>>s[i];
    sort(s+1,s+n+1);
    ans=n;
    j=1;
    zc=0;
    for(i=1;i<=n;i++){
        if(j<i) j=i;
        while(j<=n){
            if(mp[s[j]]==0) zc++;
            mp[s[j]]++;
            if(n*kbit(zc)<=8*I){
                ans=min(ans,i-1+n-j);
                j++;
            }else{
                mp[s[j]]--;
                if(mp[s[j]]==0) zc--;
                break;
            }
        }
        if(mp[s[i]]){
            mp[s[i]]--;
            if(mp[s[i]]==0) zc--;
        }
    }
    cout<<ans<<"\n";
    return 0;
}