图像压缩题解

· · 题解

图像压缩题解

题目传送门
这道题就是一个纯纯的模拟，挺费手的 问题也不是不很大

1.解题思路

  1. 遍历所输入的字符数组记录每个 16 进制灰度出现的次数，然后快排，找出出现次数前 16 的灰度值
  2. 输出前 16 个 16 进制灰度值，并且标记
  3. 再次遍历所输入的字符数组，判断每一个 16 进制灰度（是否标记）,
    如果是前 16 个灰度值就直接输出，
    否则遍历前 16 个灰度值，转换为 10 进制，查找最接近的
    并输出

2.代码方面

  1. 用结构体来记录每个灰度值的信息：16进制灰度值和出现的次数
  2. 用 stl 库里的 pair 来记录每个16进制灰度值（刚好两个字符）
  3. 用 stl 库里的 map 来标记灰度的十六进制编号和十进制灰度值

3.代码如下

#include<bits/stdc++.h>
using namespace std;
int n;
char s[30][30];
struct grey{//灰度
    pair<char,char> cl; 
    int cnt;
}gr[256];//十六进制：00 ~ FF => 十进制: 0 ~ 255（下标） 
map< pair<char,char> ,bool> bct;//是不是前十六个灰度 
map< pair<char,char> , pair<char,int> > mp;//灰度的十六进制编号和十进制灰度值 
void InitGrey(){//初始化数组 
    for(int i=0;i<256;i++) gr[i].cnt=0; 
    return;
}
int st_t(pair<char,char> st){//十六进制转十进制 
    int s1=st.first>='0'&&st.first<='9' ? st.first-'0' : st.first-'A'+10; 
    int g1=st.second>='0'&&st.second<='9' ? st.second-'0' : st.second-'A'+10; 
    return s1*16+g1; 
}
char t_st(int t){//十进制转十六进制 
    return t<10 ? t+'0' : t-10+'A';
} 
bool cmp(grey cmp1,grey cmp2){//结构体 sort快排                                 
    return cmp1.cnt==cmp2.cnt ? st_t(cmp1.cl)<st_t(cmp2.cl) : cmp1.cnt>cmp2.cnt;
}
int main()
{
    scanf("%d",&n);
    InitGrey();//初始化 
    for(int i=0;i<n;i++){
        scanf("%s",s[i]);
        for(int j=0;j<strlen(s[i]);j+=2){
            pair<char,char> gr16=make_pair(s[i][j],s[i][j+1]);//16进制灰度值 
            int gr10=st_t(gr16);//10进制灰度值
            gr[gr10].cl=gr16;
            gr[gr10].cnt++;
        }
    }
    sort(gr,gr+256,cmp);//快排 
    for(int i=0;i<16;i++){
        printf("%c%c",gr[i].cl.first,gr[i].cl.second);//输出前 16 个16进制灰度值 
        char ch=t_st(i);//十六进制编号 
        mp[gr[i].cl]=make_pair(ch,st_t(gr[i].cl));//标记前十六个灰度的六进制编号和十进制灰度值 
        bct[gr[i].cl]=true;//标记前十六个灰度 
    }
    for(int i=0;i<n;i++){
        printf("\n");
        for(int j=0;j<strlen(s[i]);j+=2){
            pair<char,char> str=make_pair(s[i][j],s[i][j+1]);
            if(bct[str]) printf("%c",mp[str].first);//是前 16 就直接输出 
            else{//不是前 16 
                int t1=st_t(str),d_min=260;
                char ch;
                for(int k=0;k<16;k++){//遍历前 16 个查找 
                    int d=abs(st_t(gr[k].cl)-t1);
                    if(d<d_min) d_min=d,ch=t_st(k);
                }
                printf("%c",ch);
            }
        }
    }
    return 0;//完结撒花 
}