- 虽然现在已经考完试挺久了，但是还是准备把复习笔记放上来
- 好消息是考试的时候那四道题我全部复习到了，坏消息是考试的时候我忘记差分约束的图怎么画了，然后第二题动态规划的递归函数我忘了，我当时脑子都烧了都想不出那题动态规划哪里有递归，考完后我才想起来，原来它说的就是
pre[]数组的递归输出函数，醉了。
二部图
Machine Schedule 1325
- 最小顶点覆盖数 = 最大匹配数
- 把任务当成一条边，每经过一个节点，就要重启一次切换模式，那么模式切换次数最少的情况就是最小顶点覆盖数
- 交错路:只要一条路径上的边，是“已匹配边”和“未匹配边”交替出现的，它就是交错路。
增广路：它首先必须是一条交错路，但它同时还有两个条件：
- 起点必须是一个未被匹配（闲置）的节点。
- 终点也必须是一个未被匹配（闲置）的节点。
- 因为两头都是闲置的，这种路径必然包含奇数条边，且“未匹配边”的数量刚好比“已匹配边”多出 1 条。
当你把这条路上的状态统统“反转”（连上的断开，没连的连上），原本冲突解开了，且总匹配数增加 1 个。这就是寻找增广路的意义。
vector,match,vis bool dfs(int s) { for->遍历s的那条链 { 取一个节temp点出来 if(!vis[temp]) { vis=true; if 对方没有恋人||对方恋人的恋人能换 { match[s]=temp; return true; } } } 遍历了一整遍都没有，说明就是连不了了 false; } int main() { while(true) { 清理adj; cin数据，n==0->break; for->循环输入(i,x,y) { 机器本来就在 0 模式，不需要重启就能完成0任务,故凡是遇到x=0或者y=0的任务，直接无视,不要把它们建到图里去-> x!=0&&y!=0才.pushback() } max_match=0; memset(match)->all=-1; for->一个一个点计算 { memset(vis)->all=0; if(dfs成功) { 最大匹配数加一 } } 这是非常明确地从机器 A（左边）连向机器 B（右边）的有向图。不用除2 cout } }
girls and boys 1466
- 求最大独立集
最大独立集 + 最小顶点覆盖（最大匹配） = 顶点总数
vector,match,vis bool dfs(int s) { ...same as former } int main() { int m; while(cin>>m) { for-> clear() and inital match[] for { scanf("%d: (%d)", &id, &num); for->cin>>好感关系 then .push_back } int match_num=0; for(不区分男女，全部m都遍历一遍，故算了两遍，答案要除2) { memset if(dfs成功)-> match_num++ } cout **记得/2** } }
Sorting Slides 1486
- 求完美匹配的不可代边
- 完美匹配：相亲现场的所有男生和所有女生，一个不落，全部成功脱单！
1.统计好感对象 2.跑一遍匈牙利 3.逐一拆散各个情侣，看看该对情侣是不是不可代替的
struct slide; struct point; bool isinside;->判断点是不是在幻灯片里面 vector,match,vis bool dfs(int s,int fu,int fv)->改进的匈牙利 ->fu和fv组成被禁止的边，fv是边的终点 ->如果不禁止任何人，传 -1 即可。 { for->沿着s那个链取点 { int v=adj[s][i];取的新边 if(s==fu and v==fv)->这是有意被拆散的边 { continue; } 后面一样 } } int main() { while(true) { int m; if(m==0) break; ------------------------------------------ vector slides,point; for->收集slide和point ------------------------------------------ for { clear() adj表 for { if(inside)->push_back; } } ------------------------------------------ 跑匈牙利algorithm ------------------------------------------ heap++ （格式要求） if match_num!=m ->连全员匹配都做不到，那必然没有唯一确定的解 { cout<<"none"; continue; } ------------------------------------------ int inital_match ; for->保存现在的完美匹配结果 ------------------------------------------ vector<pair<char, int>> ans; -> 保存最终结果 int matched_v; -> 暂存要禁止的边 for i ->定下部节点 { matched_v=-1; for j ->遍历上部节点找连接着的 { if(initial_match[j] == i)->更新matched_v } if (matched_v!=-1) { for->将match用inital_match来恢复 match[matched_v]=-1; 切断连接 } memset vis if(!dfs(i,i,match_ed))->添加到ans } ------------------------------------------ cout 答案 } }
Fire Net HDU 1045
- 求二部图最大匹配
男生集合（左）：
- 所有的“横向连通块”。
每一行从左到右扫，遇到 . 就把它编入当前的横向块。一旦遇到墙 X，或者换行了，横向块的编号就 +1（诞生了一个新的独立男生）。
女生集合（右）：所有的“纵向连通块”。
- 每一列从上到下扫，遇到 . 编入当前的纵向块。遇到墙 X 或者换列了，纵向块编号 +1。
- 例：男生：
- X 2 (遇到X或者换行，编号递增)
- 3 3 (全是空地，同属男生3号)
X 4 X - 例：女生
- X 4
- 3 4
X 3 X - 每个男生只能匹配一个女生规避了相互摧毁的可能
- 1->1,2->4,3->1...组成了好感组
- 到时候直接匈牙利求一遍最大匹配即可
- 上下两边的节点，一个就是行编号，一个就是列编号
vector,match,vis
bool dfs(int s)
{
...same as former
}
int main()
{
while(true)
{
int n;
cin>>n;
if(n==0) break;
------------------------------------------
int r_id[MAXN][MAXN] = {0}; // 记录每个点所在的横向块编号(男生)
int c_id[MAXN][MAXN] = {0}; // 记录每个点所在的纵向块编号(男生)
int r_cnt = 0; // 男生（横向块）总数
int c_cnt = 0; // 女生（纵向块）总数
------------------------------------------
统计男生
for 遍历行
{
for 遍历列
{
输入，并判断
if .->r_id[i][j] = r_cnt;
if X->r_cnt++;
}
换行也要 r_cnt++;
}
统计女生
for 遍历行
{
for 遍历列
{
输入，并判断
if .->r_id[j][i] = r_cnt;
if X->r_cnt++;
}
换行也要 r_cnt++;
}
------------------------------------------
for->adj[].clear();
------------------------------------------
开始adj[].push_back();
组好感组;
------------------------------------------
跑匈牙利
------------------------------------------
因为已经是明确的横块连纵块了，所以不用除2
cout 结果
}
}Uncle Tom's Inherited Land HDU 5780
- pond卖不了
- 只能卖两个连在一起的空地
- 这题主要就是要判断两个地块是不是连在一起，如果是连在一起的，就可以加入到好感组里，作为后续的连接备选
如何确定能不能进好感组？和上学期的迷宫寻路类似
看当前方块的上下左右有没有空格，有的话就可以加入到好感组里//寻找连接关系 for->定行 { for->定列 { if 当前块=1->continue; 说明是pond int u = i * column + j; 算格子编号 for(int k=0;k<4;k++)->遍历上下左右 { 算坐标 if 没越界 and 不是ponds->adj.push_back(); } } } 因为这样算的话，二分图没有分男女，所以最后的match_num要除2 cout match_num/2;
狼杨菜过河
- 状态转移过程符合二部图
- 只看河西岸的状态
- F：农夫 S：羊 W：狼 V：蔬菜
男生那边的节点是农夫在西岸的时候，西岸的状态
- 符合要求的有FSWV，FSW，FSV，FWV，FS
女生那边的节点是农夫在东岸的时候，西岸的状态
- 符合要求的有W，V，S，WS，无(西岸全空，目标达成)
- 手工方法就是找一条可以从 FSWV 到 无 的路线
- 从男生区到女生区是农夫从西岸到东岸，从女生区到男生区表示农夫从东岸返回西岸
最短路径
聘礼 1062
- 改进dijsktra，使用min_L,max_L来约束
暴力遍历所有约束情况即可，再每种约束情况下跑一遍dijkstra，与原先ans对比，选最小的
INF，L[105],P[105],X[105],N,M struct edge: int to 和 int weight; int dijkstra(int min_L,int max_L) ->两个边界约束了一个等级区间 { inital dist,vis; dist[0]=0;->虚拟出发节点0 --------------------------------------------- for->遍历N+1次 (because 添加了一个虚拟节点) { inital u,min_dist; --------------------------------------------- for->遍历N+1次 (目的是找当前dist最小的点作为起点) { if(!vis and dist[当前节点]<min_dist) { if(满足等级界限) { min_dist=dist[0]; u=当前节点; } } } if 没找到，即u还为-1 then break; vis[u]=true; --------------------------------------------- for->遍历adj[u]那条链 { inital v,wieght; if 满足界限 { if (dist[u] + w < dist[v]) { update; } } } --------------------------------------------- } re dist[1]; } int main() { while(cin>>M>>N) { for->依据N来遍历 { cin P L X ; adj[0].push_back({i,P[i]}); for->依据X来遍历 { cin T,V adj[i].push_back({T,V}); } } --------------------------------------------- inital ans = INF; --------------------------------------------- // 枚举合法的等级区间 // 因为 1 号必须在路径里，所以区间的下界一定在 [L[1] - M, L[1]] 之间 for (int i = L[1] - M; i <= L[1]; i++) { int current_min_L = i; int current_max_L = i + M; // 跑 Dijkstra 并取全场最小值 ans = min(ans, dijkstra(current_min_L, current_max_L)); } } cout ans }
Knight Moves 2243
- bellman ford本质是暴力松弛，暴力循环n-1次
这题每移动一步是要跑'L'型
const int INF; inital L型数组 int bellman_ford(start,end) { inital dist[65]=INF; dist[起始点]=0; for->循环64-1次 { bool update=false; for->循环64次 遍历每一个点 { if 这个点=INF then continue; 用/和%算出横竖坐标 for->遍历L型变换数组 { 算出变化后的new横竖坐标 if 检查变化后的坐标有没有出界 { if dist[u] + w < dist[v] { 松弛 跟新update=true; } } } } 如果在一整轮全图扫描中，没有任何格子的距离被更新 说明最短路径已经全部收敛，直接提前结束循环！ if update == false then break; } re dist[start]; } int main() { string startpoint,endpoint; while(cin>>startpoint,endpoint) { int start_col = startpoint[0] - 'a'; int start_row = startpoint[1] - '1'; ... endpoint same; int start_node=start_col+start_row*8; ... endpoint same; 跑bellman_ford; } }
Risk 1603
- 利用floyd最短路径算法
- floyd的核心就是找中转节点
如果通过中转节点中转得到的距离小于直达距离，那么就需要更新dist
const int INF=999999999; int dist[25][25]; void floyd() { for->遍历中转节点 { for ->遍历起始节点 { for->遍历终点 { if 中专距离小于直达距离 then 更新 } } } } int main() { inital x,test_case; while(cin>>x) { for{ for{ 初始化dist[][] if (i == j) { dist[i][j] = 0; // 自己到自己的距离为 0 } else { dist[i][j] = INF; // 初始都不互通 } } } for->输入第一个点的信息 { 建无向图 } for { for { 输入后边19个国家的信息 } } 跑floyd; 处理查询并输出 } }
burn the linked camp
- 差分约束系统
- 利用差分约束转换为图，然后跑bellman ford
一共有三个不等式：
- 常理约束 S_i - S_{i-1} >= 0
- 容量约束 S_{i-1} - S_i >= -C_i
- 情报约束 S_j - S_{i-1} >= weight
bellman ford求最长路径
const int INF=-9999999999; struct edge:int to and weight; inital n,m,vector adj[],C[](最多能容纳 Ci 名士兵); void bellman_ford() { 初始化dist[][] dist[0]=0; for { bool update=false; for { if 不可达 then continue; for 遍历adj[s] { int to,weight; if 更长 { 更新 if 已经运行到第n轮 还可以更新 说明有正环 { bad estimations } } } } //如果一整轮都没有更新，提前退出 if (!updated) break; } cout }
windows pain 2585
拓扑排序找环
inital grid[][],adj[][],has_edge[],in_degree[]; bool solve() { inital queue; for { 找入度为0的放进queue; } inital count; while queue not empty { 取出第一个; conut++; for->沿着adj(queue.front)找 { 一个接着一个入度--; if 入度==0 { queue.push_back(); } } } return count==9; } int main() { int s; while(true) { cin>>s; if s==... break; 初始化 has_edge... for { cin>>grid[][]; } 接受废物 for { for { int v=grid[r][c]; for-> w=1到9 { 计算min_c,min_r...; if 可以覆盖到 { if w != v && !has_edge[w][v] { has_edge=true; adj.push_back; in_degree++; } } } } } // 跑 拓扑排序 并且判断结果 if (topo_sort()) { cout << "THESE WINDOWS ARE CLEAN" << endl; } else { cout << "THESE WINDOWS ARE BROKEN" << endl; } } re 0; }\
miles to chicago 2472
- 变异最短路径，要求概率最大路径
- 因此在松弛的时候，用两个dist相乘即可
如果大于当前路径，则更新
struct edge; inital N,M; int dijkstra() { inital dist[]; for { int u=-1; double max_dist=-1.00; for { 找max_dist最大路; } ... same as 聘礼 ... 核心变化：概率是相乘的。如果走 u 到 v 能让 v 的存活概率更大，就更新它 if (!vis[v] && dist[u] * w > dist[v]) { dist[v] = dist[u] * w; } ... } } int main() { while(true) { cin>>N; if(N==0) break; 初始化adj[]; for { 建图 ... adj[a].push_back({b, p / 100.0}); adj[b].push_back({a, p / 100.0}); } double ans = dijkstra; cout ans; } }
frogger 2253
- 变异dijkstra
- 要找出青蛙跳跃路径上最长的那一次跳跃，然后要使那一次最长的跳跃最短
即：青蛙 Freddy 要跳到 Fiona 那里，有很多条路线可以走。每条路线都会发生很多次跳跃，我们要找出所有路线中，单次跳跃距离最大值最小的那条路线，并输出这个最小的“最大跳跃距离”
int N; double X[205], Y[205]; // 存放每个石头的 x, y 坐标 vector<Edge> adj[205]; 就把dijkstra的松弛部分改成下述代码就行： // 用 u 点去松弛更新它的邻居 for (int k = 0; k < adj[u].size(); k++) { int v = adj[u][k].to; double w = adj[u][k].weight; // 核心变化：走这条路的代价，取决于“之前最大的跳跃”和“当前这一跳”谁更大 double max_jump = max(dist[u], w); // 如果这条路的最大跳跃，比原本记录的 v 点最大跳跃要小，就更新它 if (!vis[v] && max_jump < dist[v]) { dist[v] = max_jump; } } int main() { while(true): 判断停不停 初始化 建图部分： for { cin>>X[]>>Y[]; } 计算距离，并建图： for { for { 距离公式 adj[i].push_back({j,distance}); adj[j].push_back({i,distance}); } } ans = dijkstra(); cout }
Highways 1751
- prim 最小生成树
和dijkstra很像，就是把松弛过程变成松弛节点v距离已经连通的群体的最短距离
- 在 Dijkstra 里： dist[i] 意思是从起点 1 号走到城市 i，总共要走多远(沿途累加的距离)。
- 在 Prim 里： dist[i] 意思是尚未加入群体的城市 i，如果要搭一条桥连到已经建好的群体里，最短的那座桥有多长
inital X[752],Y[752],grid[752][752]; void prim() { inital dist,vis,pre; 其他一样，就改松弛部分 if (u != 1 && graph[pre[u]][u] > 0.0) { cout << pre[u] << " " << u << endl; } // 用刚加入的 u 去更新其他未加入的城市 for (int v = 1; v <= N; v++) { // Prim 的松弛条件：不累加路径，只看当前这条边是不是比原本的桥梁更短 if (!vis[v] && graph[u][v] < dist[v]) { dist[v] = graph[u][v]; pre[v] = u; } } } int main() { ... }
士兵排队 chap03_P106
拓扑排序，改动的地方就是给toposort函数传一个vector用于接受排序队列
inital N adj[],had_edge[][],in_degree[] bool toposort(vector<int> &result) { inital queue; for 寻找入度为0节点放入queue 开始松弛 if result.size()==N then re true; } int main() { ... }
Swordfish chap03_P36
- prim
- 和Highways差不多
搜索
Eight 1077
- bfs搜索+康托展开
- 如果有偶数个逆序对，那么就无解，因为上下交换位置一次会引入两个逆序对或者减少两个逆序对
然后针对有解的八数码进行bfs搜索
树
约瑟夫问题 2746
- 利用线段树
- 递归查找要删去的节点k，如果左子树所容纳的总青蛙数量大于k，那就跑去左子树，如果小于k，那就用k减去左子树的总容量然后跑去右子树
- 在main函数中，for循环n-1次，第n次就是删除最后一个青蛙，这时候青蛙的编号为1，这一次单独拉出循环来算，然后输出这一次的答案即可
- 要注意青蛙编号和树节点编号是不一样的，二者类似于映射关系，不要搞混
Quadtree 2266
- 四分树，dfs填数
四分树 1610
#include <iostream>
#include <string>
#include <queue>
using namespace std;
// 全局数组存放图片
int img[520][520];
// 定义一个结构体，用来放进队列里
struct Node
{
int r; // 左上角行号
int c; // 左上角列号
int size; // 边长
};
// 将4位二进制字符串转为 1 个十六进制字符
char binToHex(string s)
{
int weight[] = {8, 4, 2, 1};
int val = 0;
for (int i = 0; i < 4; ++i)
{
if (s[i] == '1')
{
val += weight[i];
}
}
// 如果是 0~9 直接变成字符，如果是 10~15 变成 A~F
if (val < 10)
{
return '0' + val;
}
else
{
return 'A' + (val - 10);
}
}
void solve()
{
int N;
cin >> N;
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < N; ++j)
{
cin >> img[i][j];
}
}
queue<Node> q;
q.push({0, 0, N}); // 初始把整张大图放进队列
string bin_str = ""; // 用来收集长长的 01 序列
// 开始 BFS 宽度优先遍历
while (!q.empty())
{
Node curr = q.front();
q.pop();
int r = curr.r;
int c = curr.c;
int size = curr.size;
// 检查这个区域是不是纯色的
int first_pixel = img[r][c];
bool is_mixed = false;
for (int i = 0; i < size; ++i)
{
for (int j = 0; j < size; ++j)
{
if (img[r + i][c + j] != first_pixel)
{
is_mixed = true;
break;
}
}
if (is_mixed) break;
}
// 根据检查结果生成编码
if (is_mixed)
{
bin_str += "1"; // 杂色，节点值为1，并分裂出 4 个儿子加入排队
int half = size / 2;
q.push({r, c, half}); // 左上
q.push({r, c + half, half}); // 右上
q.push({r + half, c, half}); // 左下
q.push({r + half, c + half, half}); // 右下
}
else
{
// 纯色，不用再分了，直接输出两个数
if (first_pixel == 0)
{
bin_str += "00";
}
else
{
bin_str += "01";
}
}
}
// 二进制转十六进制
// 补齐前导 0，使得长度正好是 4 的倍数
while(bin_str.length() % 4 != 0)
{
bin_str = "0" + bin_str;
}
string hex_str = "";
// 每次抓取 4 个字符进行转换
for (int i = 0; i < bin_str.length(); i += 4)
{
hex_str += binToHex(bin_str.substr(i, 4));
}
// 抹除十六进制最前面的那些无用的 '0' (但是要保留至少一个字符，比如结果就是 0 的情况)
int start_idx = 0;
while (start_idx < hex_str.length() - 1 && hex_str[start_idx] == '0')
{
start_idx++;
}
// 输出最终结果
cout << hex_str.substr(start_idx) << endl;
}
int main()
{
int k;
if (cin >> k)
{
while (k--)
{
solve();
}
}
return 0;
}DP
fatmouse 1160
- 动态规划
- 先选出最后一只老鼠，然后从最后一只老鼠开始向前查看，看看前面任意一只老鼠序列+1后会不会比当前这只老师所已经存好的序列长，如果是，那么就更新，然后更新前驱
Common Subsequence 1458
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
int main()
{
string a, b;
while (cin >> a >> b)
{
int lena = a.length() + 1;
int lenb = b.length() + 1;
int v[lena][lenb];
for (int i = 0; i < lena; i++)
{
for (int j = 0; j < lenb; j++)
{
v[i][j] = 0;
}
}
// 状态转移方程
for (int i = 1; i < lena; i++)
{
for (int j = 1; j < lenb; j++)
{
if (a[i - 1] == b[j - 1])
{
v[i][j] = v[i - 1][j - 1] + 1;
}
else
{
v[i][j] = max(v[i - 1][j], v[i][j - 1]);
}
}
}
cout << v[lena - 1][lenb - 1] << '\n';
}
return 0;
}Human Gene Functions 1080
#include <iostream>
#include <string>
#include <algorithm> // 用于 max()
using namespace std;
// 1. 老规矩，在全局开二维数组，大小 105 绝对够用
int dp[105][105];
// 辅助函数：把字母变成 0,1,2,3,4 的索引，方便查表
int getIdx(char c) {
if (c == 'A') return 0;
if (c == 'C') return 1;
if (c == 'G') return 2;
if (c == 'T') return 3;
return 4; // '-'
}
// 辅助函数：查询两个字符匹配的得分（这个表题目会给，考场上照抄即可）
int getScore(char a, char b) {
int scoreMatrix[5][5] = {
{ 5, -1, -2, -1, -3}, // A
{-1, 5, -3, -2, -4}, // C
{-2, -3, 5, -2, -2}, // G
{-1, -2, -2, 5, -1}, // T
{-3, -4, -2, -1, 0} // -
};
return scoreMatrix[getIdx(a)][getIdx(b)];
}
void solve() {
int len1, len2;
string s1, s2;
// 读入长度和字符串
cin >> len1 >> s1 >> len2 >> s2;
// 2. 初始边界状态（重要防坑点！）
// 刚才的 LCS 题，一边为空时公共长度直接是 0。
// 但这题不行！如果一边为空，另一边必须全和 '-' 匹配，这会扣分！
dp[0][0] = 0;
for (int i = 1; i <= len1; ++i) {
// s1 的前 i 个字符，去和 s2 的空串（也就是全是 '-'）匹配
dp[i][0] = dp[i - 1][0] + getScore(s1[i - 1], '-');
}
for (int j = 1; j <= len2; ++j) {
// s2 的前 j 个字符，去和 s1 的空串匹配
dp[0][j] = dp[0][j - 1] + getScore('-', s2[j - 1]);
}
// 3. 核心双层循环 (你最熟悉的结构)
for (int i = 1; i <= len1; ++i) {
for (int j = 1; j <= len2; ++j) {
// 当前面对 s1 的字符和 s2 的字符，我们有 3 种选择：
// 选择 A：让它俩直接配对
int choiceA = dp[i - 1][j - 1] + getScore(s1[i - 1], s2[j - 1]);
// 选择 B：s1 的当前字符去和 空格 '-' 配对 (s2 不出人)
int choiceB = dp[i - 1][j] + getScore(s1[i - 1], '-');
// 选择 C：s2 的当前字符去和 空格 '-' 配对 (s1 不出人)
int choiceC = dp[i][j - 1] + getScore('-', s2[j - 1]);
// 利益权衡：取这三种选择里得分最高的一个！
dp[i][j] = max(choiceA, max(choiceB, choiceC));
}
}
// 输出右下角的最终结果
cout << dp[len1][len2] << endl;
}
int main() {
int t;
if (cin >> t) {
while (t--) {
solve();
}
}
return 0;
}huffman编码
Entropy 1521
#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <iomanip> // 用于控制保留一位小数
using namespace std;
// 1. 你的习惯：全局数组，存放 256 个 ASCII 字符的出现频率
int freq[300];
int main()
{
string s;
// 经典多组读入，遇到 "END" 结束
while (cin >> s && s != "END")
{
// 每次处理前，老老实实把频率数组清零
for (int i = 0; i < 300; ++i)
{
freq[i] = 0;
}
// 统计字符串中每个字符出现的次数
for (int i = 0; i < s.length(); ++i)
{
freq[s[i]]++;
}
// 2. 考场神兵利器：最小堆（优先队列）
// priority_queue 默认是最大堆，加上 greater<int> 就变成了最小堆，队头永远是最小的数
priority_queue<int, vector<int>, greater<int>> pq;
// 把所有出现过的字符的频率，扔进队列里
for (int i = 0; i < 300; ++i)
{
if (freq[i] > 0)
{
pq.push(freq[i]);
}
}
// ASCII 编码的固定长度：每个字符占 8 bit
int ascii_len = s.length() * 8;
int huffman_len = 0;
// 3. 防坑特判：如果整个字符串只有一种字符 (比如 "AAAA")
// 按照 Huffman 规则，唯一的字符只需要 1 个 bit，所以总长等于原字符串长度
if (pq.size() == 1)
{
huffman_len = s.length();
}
else
{
// 4. 核心逻辑：合并果子 (模拟 Huffman 树合并)
while (pq.size() > 1)
{
// 每次挑出频率最小的两个节点
int a = pq.top();
pq.pop();
int b = pq.top();
pq.pop();
// 把它们合并成一个新节点
int sum = a + b;
// 【绝妙规律】把每次合并的值累加起来，正好等于最终编码的总长！
huffman_len += sum;
// 把新节点扔回堆里继续参与合并
pq.push(sum);
}
}
// 5. 计算压缩比 (记得把整数转成 double)
double ratio = (double)ascii_len / huffman_len;
// 按照要求输出：原长、压缩后长、保留一位小数的压缩比
cout << ascii_len << " " << huffman_len << " "
<< fixed << setprecision(1) << ratio << endl;
}
return 0;
}
评论已关闭