目录
补强：
这里对上一期的第二题进行一个单独的加强，这里有一个新的思路和代码来和大家分享。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
// 使用vector来存储每段木头的长度，用于初始化优先队列
vector<int> lengths(n);
for (int i = 0; i < n; ++i)
{
cin >> lengths[i];
}
// 定义优先队列（小顶堆），用于存放当前待合并的木头长度
priority_queue<int, vector<int>, greater<int>> pq;
for (int length : lengths)
{
pq.push(length);
}
int result = 0;
//定义了一个优先队列 pq，它的元素类型为 int（存放木头长度数值），
底层容器使用 vector<int>，并且通过 greater<int> 作为比较函数，
使得这个优先队列成为一个小顶堆，也就是队列中优先级最高（排在最前面，每次 top 函数获取的就是它）的元素是值最小的元素。
接着使用范围 for 循环遍历 lengths 向量，将每段木头的长度依次压入优先队列 pq 中，为后续的合并操作准备数据，此时优先队列中按照木头长度从小到大排列了所有的初始木头段长度。
// 只要优先队列中还有超过1个元素，就继续合并操作
while (pq.size() > 1)
{
int first = pq.top();
pq.pop();
int second = pq.top();
pq.pop();
int sum = first + second;
result += sum;
pq.push(sum);
}
cout << result << endl;
return 0;
}这段代码比较简单，大家直接看就可以看的懂，这里简单说一下，我们利用优先队列来简化我们的排列（这就是最关键的一步，如此我们就可以不用建树来完成小根堆的排序，利于后面地加和计算），然后我们再写一个循环只要队列不唯一就会持续加和。
A3. PAT 考试排名汇总 (☆☆)
【题目描述】PTA(数据结构与算法题目集 7-41)
计算机程序设计能力考试（Programming Ability Test，简称 PAT）旨在通过统一组织的在线考试及 自动评测方法客观地评判考生的算法设计与程序设计实现能力，科学的评价计算机程序设计人才， 为企业选拔人才提供参考标准。每次考试会在若干个不同的考点同时举行，每个考点用局域网，产 生本考点的成绩。考试结束后，各个考点的成绩将即刻汇总成一张总的排名表。现在就请你写一个 程序自动归并各个考点的成绩并生成总排名表。
【输入格式】
输入的第一行给出一个正整数 N（≤100），代表考点总数。随后给出 N 个考点的成绩，格式为：首 先一行给出正整数 K（≤300），代表该考点的考生总数；随后 K 行，每行给出 1 个考生的信息，包 括考号（由 13 位整数字组成）和得分（为[0,100]区间内的整数），中间用空格分隔。
【输出格式】
首先在第一行里输出考生总数。随后输出汇总的排名表，每个考生的信息占一行，顺序为：考号、 最终排名、考点编号、在该考点的排名。其中考点按输入给出的顺序从 1 到 N 编号。考生的输出须 按最终排名的非递减顺序输出，获得相同分数的考生应有相同名次，并按考号的递增顺序输出。
【输入样例】
2
5
1234567890001 95
1234567890005 100
1234567890003 95
1234567890002 77
1234567890004 85
4
4
1234567890013 65
1234567890011 25
1234567890014 100
1234567890012 85
【输出样例】
9
1234567890005 1 1 1
1234567890014 1 2 1
1234567890001 3 1 2
1234567890003 3 1 2
1234567890004 5 1 4
1234567890012 5 2 2
1234567890002 7 1 5
1234567890013 8 2 3
1234567890011 9 2 4
————————————————
要点剖析：
- 排序的规则实现
- 对各个考点内部的排序
- 对整个考点的综合排序
逐步分析：
我们只要完成前两点，那么最后一点其实就是同理可得。首先我们要将学生按成绩排名，然后成绩相同的按学号排名，之后对两个考点的学生分别进行排名，然后汇总到一起进行最终排名。要求不是很难，但是数据很多，所以我们的代码就要尽量别出错。
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
//定义结构体表示考生信息
struct Student
{
string exam_number; // 考号
int score; // 成绩
int site_number; // 考点编号
int site_rank; // 考点内排名
};
// 自定义比较函数，用于排序（先按成绩降序，成绩相同按考号升序）
bool compare(const Student& a, const Student& b)
{
if (a.score!= b.score)
{
return a.score > b.score;
}
return a.exam_number < b.exam_number;
}
int main()
{
int site_count; // 考点总数
cin >> site_count;
vector<Student> all_students; // 存储所有考生信息的线性表
// 遍历每个考点
for (int i = 0; i < site_count; ++i)
{
int student_count; // 当前考点的考生数量，这里仍使用int类型接收输入，但后续转换使用
cin >> student_count;
vector<Student> site_students; // 存储当前考点考生信息的线性表
// 将int类型的student_count转换为size_t类型用于循环比较//是无符号整数类型
for (size_t j = 0; static_cast<size_t>(student_count) > j; ++j)
{
Student s;
cin >> s.exam_number >> s.score;
s.site_number = i + 1;
s.site_rank = 0;
site_students.push_back(s);
}
// 对当前考点考生按规则排序
sort(site_students.begin(), site_students.end(), compare);
// 确定当前考点考生的排名
size_t rank = 1;
for (size_t k = 0; k < site_students.size(); ++k)
{
if (k > 0 && site_students[k].score!= site_students[k - 1].score)
{
rank = k + 1;
}
site_students[k].site_rank = rank;
all_students.push_back(site_students[k]);
}
}
// 对所有考生按规则排序
sort(all_students.begin(), all_students.end(), compare);
// 输出考生总数
cout << all_students.size() << endl;
// 确定并输出所有考生的最终排名及相关信息
size_t final_rank = 1;
for (size_t m = 0; m < all_students.size(); ++m)
{
if (m > 0 && all_students[m].score!= all_students[m - 1].score)
{
final_rank = m + 1;
}
cout << all_students[m].exam_number << " " << final_rank << " " << all_students[m].site_number << " " << all_students[m].site_rank << endl;
}
return 0;
}代码分析：
bool compare(const Student& a, const Student& b)
{
if (a.score!= b.score)
{
return a.score > b.score;
}
return a.exam_number < b.exam_number;
}
这是一个自定义的比较函数，用于为排序操作提供比较规则。它接受两个 Student 结构体类型的常引用作为参数，按照以下逻辑进行比较：
首先比较两个考生的成绩 score，如果成绩不同，那么按照成绩从高到低进行排序，即成绩高的考生排在前面，所以返回 a.score > b.score。
如果两个考生的成绩相等，再比较他们的考号 exam_number，按照考号从小到大进行排序（字典序比较），此时返回 a.exam_number < b.exam_number，使得考号小的考生在成绩相同的情况下排在前面。 // 遍历每个考点
for (int i = 0; i < site_count; ++i)
{
int student_count; // 当前考点的考生数量，这里仍使用int类型接收输入，但后续转换使用
cin >> student_count;
vector<Student> site_students; // 存储当前考点考生信息的线性表
// 将int类型的student_count转换为size_t类型用于循环比较//是无符号整数类型
for (size_t j = 0; static_cast<size_t>(student_count) > j; ++j)
{
Student s;
cin >> s.exam_number >> s.score;
s.site_number = i + 1;
s.site_rank = 0;
site_students.push_back(s);
}
// 对当前考点考生按规则排序
sort(site_students.begin(), site_students.end(), compare);
// 确定当前考点考生的排名
size_t rank = 1;
for (size_t k = 0; k < site_students.size(); ++k)
{
if (k > 0 && site_students[k].score!= site_students[k - 1].score)
{
rank = k + 1;
}
site_students[k].site_rank = rank;
all_students.push_back(site_students[k]);
}
}
外层 for 循环遍历每个考点，循环变量 i 从 0 到 site_count - 1。对于每个考点：
首先定义一个整型变量 student_count，并通过 cin 读取当前考点的考生数量。接着创建一个 vector<Student> 类型的局部容器 site_students，用于临时存储当前考点的考生信息。
然后通过内层 for 循环，根据读取的考生数量，逐个读取考生的考号和成绩信息，创建 Student 结构体对象 s，将考号和成绩赋值给对应的成员变量，同时将考点编号设置为当前循环的 i + 1（因为考点编号从 1 开始计数），考点内排名初始化为 0，再将该考生对象 s 压入 site_students 容器中，这样就完成了当前考点所有考生信息的录入。
调用 sort 函数，传入 site_students 容器的起始迭代器和结束迭代器以及自定义比较函数 compare，按照之前定义的规则（先按成绩降序，成绩相同按考号升序）对当前考点的考生信息进行排序，方便后续确定排名。
再通过一个 for 循环来确定当前考点考生的排名：初始化一个 size_t 类型的变量 rank 为 1，表示初始排名为第一名。在循环中，通过比较相邻考生的成绩，如果当前考生成绩与前一位考生成绩不同，说明排名需要更新，将 rank 设置为当前循环变量 k + 1，然后将当前考生的考点内排名 site_rank 成员变量赋值为这个 rank 值，并将该考生信息压入 all_students 容器中，最终 all_students 容器就包含了所有考点的所有考生信息，并且每个考生都有了在其考点内的排名。
// 对所有考生按规则排序
sort(all_students.begin(), all_students.end(), compare);
这一步调用 sort 函数对存储所有考生信息的 all_students 容器按照之前定义的比较规则（先成绩降序，成绩相同考号升序）再次进行排序，目的是为了确定所有考生的最终排名（跨考点的整体排名）做准备。由于篇幅关系，对于结构体的定义和输出这里就不多赘述。
实验结果：
A4. 旅游规划问题 (☆☆)
【题目描述】PTA(数据结构与算法题目集 7-9)
有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需 要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径 都是最短的，那么需要输出最便宜的一条路径。
【输入格式】
输入数据的第 1 行给出 4 个正整数 n、m、s、d，其中 n（2≤n≤500）是城市的个数，顺便假 设城市的编号为 0~(n−1)；m 是高速公路的条数；s 是出发地的城市编号；d 是目的地的城市编号。 随后的 m 行中，每行给出一条高速公路的信息，分别是：城市 1、城市 2、高速公路长度、收费额，中间用空格分开，数字均为整数且不超过 500。输入保证解的存在。
【输出格式】
在一行里输出路径的长度和收费总额，数字间以空格分隔，输出结尾不能有多余空格。
【输入样例】
4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20
【输出样例】
3 40
————————————————
要点剖析：
- 首先就是构建无向图，对于图的构建和初始化有一定理解。
- 然后对于各个边线的权值进行比较（比较城市之间的公路长度，收费额）
逐步分析：
- 对于无向图的构建和初始化这个没什么好说的，中规中矩。唯一要注意的一点就是无向图的无向二字，我们对于一个变现的定义要双方都进行。
- 权值的比较我们可以直接对于公路的长度的比较进行第一次比较，然后对于收费额进行第二次比较。
#include<bits/stdc++.h>
using namespace std;
const int INF = INT_MAX;//表示不可达
// 边的结构体
struct Edge
{
int to;//指向的节点
int length;
int cost;
};
// 图的结构体，使用邻接表表示
struct Graph
{
vector<vector<Edge>> adjList;//内是节点编号，外是便结构体信息
Graph(int n) : adjList(n) {}//初始化
void addEdge(int from, int to, int length, int cost)
{
adjList[from].push_back({to, length, cost});
adjList[to].push_back({from, length, cost});
}
};
// 结构体用于在优先队列中比较节点
struct Node
{
int city;
int dist;
int cost;
Node(int c, int d, int co) : city(c), dist(d), cost(co) {}
bool operator>(const Node& other) const // 重载>
{
if (dist == other.dist)
return cost > other.cost;
return dist > other.dist;
}
};
// 实现Dijkstra算法找到最短路径及最便宜路径
pair<int, int> dijkstra(Graph& g, int s, int d) //起点s，目标d
{
int n = g.adjList.size();
vector<int> dist(n, INF);
vector<int> cost(n, INF);
priority_queue<Node, vector<Node>, greater<Node>> pq;
dist[s] = 0;
cost[s] = 0;
pq.push(Node(s, 0, 0));
while (!pq.empty())
{
Node current = pq.top();
pq.pop();
if (current.city == d)
return make_pair(dist[d], cost[d]);
if (current.dist > dist[current.city] || current.cost > cost[current.city])
continue;
for (const Edge& edge : g.adjList[current.city]) //遍历current.city的邻接表
{
int newDist = dist[current.city] + edge.length;
int newCost = cost[current.city] + edge.cost;
if (newDist < dist[edge.to] || (newDist == dist[edge.to] && newCost < cost[edge.to]))
{
dist[edge.to] = newDist;
cost[edge.to] = newCost;
pq.push(Node(edge.to, newDist, newCost));
}
}
}
return make_pair(dist[d], cost[d]);
}
int main()
{
int n, m, s, d;//节点个数，图的边数，初始节点，目标节点
cin >> n >> m >> s >> d;
Graph g(n);
for (int i = 0; i < m; ++i)
{
int city1, city2, length, cost;
cin >> city1 >> city2 >> length >> cost;
g.addEdge(city1, city2, length, cost);
}
pair<int, int> result = dijkstra(g, s, d);
cout << result.first << " " << result.second << endl;
return 0;
}代码分析：
// 结构体用于在优先队列中比较节点
struct Node
{
int city;
int dist;
int cost;
Node(int c, int d, int co) : city(c), dist(d), cost(co) {}
bool operator>(const Node& other) const // 重载>
{
if (dist == other.dist)
return cost > other.cost;
return dist > other.dist;
}
};
用于在优先队列中表示图中的节点状态，包含三个成员变量：
int city：表示节点的编号，用于标识是图中的哪个节点。
int dist：记录从起始节点到当前节点的距离（或者说路径长度）。
int cost：表示从起始节点到当前节点所花费的总成本。
构造函数 Node(int c, int d, int co) : city(c), dist(d), cost(co) {}：方便初始化 Node 结构体对象，传入节点编号、距离和成本三个参数来创建一个表示节点状态的对象。
重载了 > 运算符，用于为优先队列提供比较规则，比较逻辑是：先比较距离 dist，如果距离相等，再比较花费 cost，按照距离小优先，距离相同花费小优先的原则来确定节点在优先队列中的优先级，使得优先队列能根据这个规则弹出优先级高（距离短且花费少）的节点。// 实现Dijkstra算法找到最短路径及最便宜路径
pair<int, int> dijkstra(Graph& g, int s, int d) //起点s，目标d
{
int n = g.adjList.size();
vector<int> dist(n, INF);
vector<int> cost(n, INF);
priority_queue<Node, vector<Node>, greater<Node>> pq;
dist[s] = 0;
cost[s] = 0;
pq.push(Node(s, 0, 0));
while (!pq.empty())
{
Node current = pq.top();
pq.pop();
if (current.city == d)
return make_pair(dist[d], cost[d]);
if (current.dist > dist[current.city] || current.cost > cost[current.city])
continue;
for (const Edge& edge : g.adjList[current.city]) //遍历current.city的邻接表
{
int newDist = dist[current.city] + edge.length;
int newCost = cost[current.city] + edge.cost;
if (newDist < dist[edge.to] || (newDist == dist[edge.to] && newCost < cost[edge.to]))
{
dist[edge.to] = newDist;
cost[edge.to] = newCost;
pq.push(Node(edge.to, newDist, newCost));
}
}
}
return make_pair(dist[d], cost[d]);
}
初始化相关数据结构：
首先获取图 g 中节点的数量 n，通过 g.adjList.size() 得到。
创建两个 vector<int> 类型的数组 dist 和 cost，长度都为 n，并初始化为 INF，分别用于记录从起始节点到各个节点的最短距离和最小花费，初始化为 INF 表示尚未确定可达的最短距离和花费情况。
创建一个优先队列 pq，其元素类型为 Node，底层容器为 vector<Node>，并且通过 greater<Node> 来指定比较规则（即按照之前 Node 结构体中重载的 > 运算符定义的距离短且花费少优先的规则），用于存储待扩展的节点信息。
将起始节点 s 的距离 dist[s] 和花费 cost[s] 都初始化为 0，表示从起始节点到自身的距离和花费为 0，然后将起始节点对应的 Node 结构体对象（包含节点编号 s、距离 0、花费 0）压入优先队列 pq 中，作为算法开始的起点。
主循环扩展节点：
进入 while 循环，只要优先队列 pq 不为空，就执行以下操作：
通过 pq.top() 获取优先队列中优先级最高（即距离当前起始节点最近且花费最少）的节点信息，存储在 current 变量中，然后使用 pq.pop() 将该节点从队列中移除，表示开始对这个节点进行扩展处理。
判断当前节点 current.city 是否就是目标节点 d，如果是，说明已经找到了到达目标节点的最短路径和最小花费，直接返回一个 pair<int, int> 类型的数据，其中包含了目标节点的最短距离 dist[d] 和最小花费 cost[d]。
接着进行一个剪枝判断，如果当前获取到的节点 current 的距离 current.dist 大于已经记录的从起始节点到该节点的距离 dist[current.city]，或者当前节点的花费 current.cost 大于已经记录的到该节点的花费 cost[current.city]，说明这个节点的信息已经不是最优的了（因为之前可能已经通过其他更短路径或者花费更少的路径到达过该节点并更新了相应的距离和花费信息），直接跳过本次循环，继续处理下一个队列中的节点。
遍历当前节点 current.city 的邻接表 g.adjList[current.city]，对于每一条邻接边 edge：
计算通过当前节点到达邻接节点 edge.to 的新距离 newDist，即当前节点的距离 dist[current.city] 加上这条边的长度 edge.length。
计算通过当前节点到达邻接节点 edge.to 的新花费 newCost，即当前节点的花费 cost[current.city] 加上这条边的花费 edge.cost。
然后进行更新判断，如果新距离 newDist 小于已经记录的到邻接节点 edge.to 的距离 dist[edge.to]，或者新距离相等但新花费 newCost 小于已经记录的到邻接节点的花费 cost[edge.to]，说明找到了一条更优的路径到达邻接节点，此时更新邻接节点的距离 dist[edge.to] 和花费 cost[edge.to] 为新计算的值，并将包含邻接节点编号、新距离、新花费的 Node 结构体对象压入优先队列 pq 中，以便后续继续扩展这个邻接节点。
循环结束返回结果：
如果循环结束后还没有找到目标节点（即优先队列遍历完了但没到达目标），仍然返回一个 pair<int, int> 类型的数据，包含目标节点的距离 dist[d] 和花费 cost[d]，不过此时的值可能是 INF，表示无法从起始节点到达目标节点。对于图和边的结构体这里就不再赘述，大家可以自己看代码。
实验结果：
到这里分享的实验题目就全部分享完毕，大家对这类题感兴趣的话可以自行在PTA平台进行 自我测试，其中的题目都很不错。
标签：下篇,原题,int,site,PTA,考点,cost,dist,节点 From： https://blog.csdn.net/2301_81280642/article/details/144571130