自动搬运

查看原文

来自洛谷，原作者为

	ZsH68122zSh 大鹏一日同风起，扶摇直上九万里

搬运于2025-08-24 21:15:28，当前版本为作者最后更新于2024-03-17 17:37:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

图像压缩题解

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

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;//完结撒花 
}