GESP 题解库 / 4 级题解 / [GESP202306 四级] 图像压缩 · 第 20 / 25 题
GESP202306 四级 · B3851 · 中等

图像压缩

把 256 级灰阶压缩为 16 级:取出现次数最多的 16 种灰阶编号 0~F,其余归到最近的。

📊
n ≤ 20 行
图像行数
🔢
0 ~ 255
灰阶范围
⚡
O(n × 像素)
时间复杂度
🎯
统计 + 排序 + 映射
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

256 级灰阶图像中,每个像素取值为 00 ~ FF(0 ~ 255)。现要压缩为 16 级(0 ~ 15)。规则:

  1. 统计每种灰阶出现的数量,取数量最多的前 16 种(数量相同时,灰阶值小的优先)
  2. 这 16 种灰阶分别编号 0 ~ F,最多的编号为 0,依次类推
  3. 其他灰阶转换到最近的那 16 种之一(灰阶值之差的绝对值最小;若相同则取编号较小的那一种)

输出第一行为 16 种选定灰阶的十六进制编码(共 32 个字符);之后 n 行输出压缩后的图像,每个像素用一位十六进制表示。

💡
人话翻译:分三步走:① 统计频次 → ② 按规则选出 16 种代表灰阶并编号 → ③ 把每个像素映射到最近的编号。最容易错的是第二步的排序规则(次数降序,次数相同则灰阶值升序)和第三步的并列取小。

🔍 关键词提取

频次统计多关键字排序最近邻映射十六进制格式化

已知条件

项目说明
输入第一行 n(10 ~ 20);随后 n 行等长偶数字符串,每 2 字符一个像素
输出第一行 32 个十六进制字符;随后 n 行每个像素一位十六进制
数据范围10 ≤ n ≤ 20,每行最多 20 个像素
保证输入至少含 16 种不同灰阶
灰阶值0 ~ 255(十六进制 00 ~ FF)

需要解决的问题

02
思维导图
整理解题思路的全貌
🖼️ 统计 → 选16种 → 映射
📊 统计
开 count[256] 数组
每读一个像素计数加 1
按十六进制解析
共 n × 每行像素数
🔝 选前16
按 (次数降序, 灰阶升序) 排序
取前 16 种
依次编号 0~F
记录它们的灰阶值
🔁 映射
对每个像素值 v
在 16 种里找 |v−g| 最小
并列取编号小的
输出对应编号的十六进制
⚠️ 易错点
并列规则搞反
第一行要 32 字符(含补 0)
像素解析按两位十六进制
输出每像素一位
03
样例手算推导
构造一个简单例子走完全流程

🧮 用一个小例子说明流程

假设图像只有 5 种灰阶(真实题目至少 16 种,这里只为演示流程):

第 1 步:统计频次

灰阶值出现次数
0x105 次
0x203 次
0x303 次
0x401 次
0x501 次

第 2 步:按 (次数降序, 灰阶值升序) 排序

排序后灰阶值次数编号
第 1 位0x1050
第 2 位0x2031
第 3 位0x3032
第 4 位0x4013
第 5 位0x5014

第 3 步:映射

原灰阶与各代表的最短距离映射到编号
0x10与 0x10 距离 00
0x20与 0x20 距离 01
0x28与 0x20 差 8、与 0x30 差 8 → 并列取编号小的1
0x48与 0x40 差 8、与 0x50 差 8 → 并列取编号小的3
🔑
两个关键规则必须记清:① 选前 16 种时,若次数相同,灰阶值小的排前面(对应编号更小);② 映射时若距离并列,取编号小的那一种。因为代表灰阶本身是按"次数降序"排的,"编号小的"通常也是"出现得更多的",这样映射更合理。

🧮 输出格式要看清

输出的第一行是 32 个字符,把这 16 种灰阶的十六进制依次写出、中间不加空格。

格式正确写法错误写法
第一行10203040...(32 字符连写)10 20 30 40(有空格)
压缩后的像素每个像素一位十六进制,如 A写成两位如 0A
⚠️
为什么第一行要补 0?因为灰阶值最小可能是 0x00,如果不补 0,输出会变成 0 一位,导致总长度不是 32,格式判错。所以必须用 %02X 保证每项两位。
04
解法对比
直接枚举 16 种求最近 vs 二分查找

⚔️ 解法对比

🟢 枚举 16 种求最近(推荐) 推荐

对每个像素,在 16 个代表灰阶里线性找最近的

  • 时间 O(n × 像素 × 16)
  • 每行最多 20 像素、n ≤ 20
  • 总共约 6400 次比较
  • 代码 10 行
💡
为什么够用:图像最多个 20 × 20 = 400 个像素,每个只在 16 个候选里比一遍,总运算量不到 1 万次,完全没必要优化。

🟠 预处理映射表

预先算好 256 个灰阶值各自的映射编号,之后 O(1) 查询

  • 预处理 O(256 × 16)
  • 查询 O(1)
  • 代码稍长
  • 对本题是过度设计
⚠️
什么时候值得:如果像素数量极大(比如 1000 × 1000 = 10⁶),预处理映射表能把每次查询降到 O(1),能省下约 15 倍的常数。本题规模小,直接算即可。

📈 性能对比

方案本题运算量代码量
枚举 16 种约 6400 次约 10 行
预处理映射表约 4000 + 400 次约 18 行
05
算法流程图
统计 → 选 16 → 映射输出
开始读入 n;count[256] 清零逐行读入,每 2 个字符解析为 1 个像素,count 对应位加 1把 0~255 中出现的灰阶按 (次数降序, 灰阶值升序) 排序取前 16 种,记为 g[0..15],编号即下标输出第一行:16 种灰阶的 %02X 连写对每个像素值 v:找 |v − g[k]| 最小的 k(并列取最小 k)输出所有像素的编号(一位十六进制)结束逐像素映射
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🖼️ 图像压缩演示器

输入若干灰阶值(0~255,空格分隔),程序会选出 16 种代表灰阶并给出映射表。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

#include <bits/stdc++.h>
using namespace std;

int cntv[256];          // 各灰阶出现次数

int main() {
    int n;
    scanf("%d", &n);

    vector<string> img(n);
    for (int i = 0; i < n; i++) {
        cin >> img[i];
        // 每 2 个字符是一个像素(十六进制)
        for (size_t j = 0; j + 1 < img[i].size(); j += 2) {
            int v = stoi(img[i].substr(j, 2), nullptr, 16);
            cntv[v]++;
        }
    }

    // 收集出现过的灰阶,按 (次数降序, 灰阶值升序) 排序
    vector<int> vals;
    for (int v = 0; v < 256; v++) if (cntv[v] > 0) vals.push_back(v);
    sort(vals.begin(), vals.end(), [](int a, int b) {
        if (cntv[a] != cntv[b]) return cntv[a] > cntv[b];
        return a < b;
    });

    // 取前 16 种作为代表
    vector<int> rep(vals.begin(), vals.begin() + 16);

    // 第一行:32 个十六进制字符
    for (int k = 0; k < 16; k++) printf("%02X", rep[k]);
    printf("\n");

    // 输出压缩后的图像
    for (int i = 0; i < n; i++) {
        for (size_t j = 0; j + 1 < img[i].size(); j += 2) {
            int v = stoi(img[i].substr(j, 2), nullptr, 16);
            // 在 16 种代表里找距离最小的;并列时保留更小的编号
            int bestK = 0, bestD = INT_MAX;
            for (int k = 0; k < 16; k++) {
                int d = abs(v - rep[k]);
                if (d < bestD) { bestD = d; bestK = k; }   // 严格小于 -> 并列取小编号
            }
            printf("%X", bestK);
        }
        printf("\n");
    }
    return 0;
}
🔑
为什么用 d < bestD 而不是 d <= bestD?题目要求"绝对差相同时,编号较小的更近"。用严格小于更新时,只有"更近"才会替换当前答案——遇到相同距离时保留原来的(也就是编号更小的),恰好符合题意。这类"并列取最优"的题都用这个技巧。

📖 关键几行怎么看

代码作用为什么这样写
stoi(s.substr(j,2), nullptr, 16)解析十六进制像素每 2 个字符一个像素
排序 lambda选前 16 种次数降序、灰阶值升序
printf("%02X", rep[k])第一行%02X 保证两位,总长恰好 32
if (d < bestD)最近邻严格小于 → 并列自动取小编号
⚠️
三个坑:① 第一行漏掉补 0(比如灰阶 5 输出成 "5" 而不是 "05");② 排序时次数相同的没有按灰阶值升序;③ 压缩后的像素输出成两位(应该一位)。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
16 个不同灰阶各出现 1 次按灰阶值升序取前 16 种次数全相同 → 灰阶值小的优先
某灰阶出现次数最多该灰阶编号为 0次数最多者编号 0
距离并列的灰阶映射到编号较小的那一种第 0 种 0x10、第 1 种 0x20,则 0x18 映射到 0
第一行长度必须是 32 个字符每项两位十六进制
压缩后像素每个像素一位十六进制如编号 10 输出 A
✅
自查清单:① 排序键对了吗?② 第一行是 32 字符吗?③ 并列取小编号了吗?

🚨 易错点清单

⚠️
并列规则搞反:题目要求并列时取编号较小的,用严格小于更新即可自动满足。
⚠️
第一行长度不对:必须每项两位(%02X),总长恰好 32。
⚠️
像素解析方式错:输入每 2 个字符是一个像素(十六进制),不是每 1 个字符。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n × 像素 × 16)
空间复杂度
O(1)
n 最大
20
像素总数
≤ 400

时间怎么算的?

空间都用在哪?

一个 256 长度的计数数组和若干小数组。

✅ 规模极小,任何实现都瞬间完成。这题的难点在于把三条规则都实现正确,而不是效率。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 十六进制解析与输出
int v = stoi("AF", nullptr, 16);   // 175
printf("%02X", 175);               // "AF"(两位大写)
printf("%X", 10);                  // "A"(一位)

// 多关键字排序(次数降序,值升序)
sort(vals.begin(), vals.end(), [](int a, int b) {
    if (cntv[a] != cntv[b]) return cntv[a] > cntv[b];
    return a < b;
});

// 并列取最优(保留最先遇到的)
int best = 0, bestD = INT_MAX;
for (int k = 0; k < 16; k++) {
    int d = abs(v - rep[k]);
    if (d < bestD) { bestD = d; best = k; }   // 严格小于
}

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
多关键字排序主键降序、次键升序排行榜、Top-K 统计
并列取最优严格小于更新最近邻、最小值多个并列的题目
十六进制格式化%02X / %X所有需要固定/可变宽度十六进制输出的题
🌟
思考题:如果量化规则改成"按区间均分"(即 0~15 映射到 0、16~31 映射到 1,以此类推),压缩会有什么不同?(提示:等分量化不依赖图像内容,实现简单但效果差——如果图像大部分像素集中在某个窄区间(比如 100~120),等分量化会把这些像素压到同一级,丢失大量细节。本题的"按频次选代表"正是自适应量化的关键思想。)