仿网站被封怎么办,建设音乐网站,做网站封面素材图,京东商城网站怎么做目录
1. 最短路径算法#xff08;Dijkstra算法#xff09;
应用场景#xff1a;
优先队列的作用#xff1a;
2. 最小生成树算法#xff08;Prim算法#xff09;
应用场景#xff1a;
优先队列的作用#xff1a;
3. 哈夫曼编码#xff08;Huffman Coding#x…
目录
1. 最短路径算法Dijkstra算法
应用场景
优先队列的作用
2. 最小生成树算法Prim算法
应用场景
优先队列的作用
3. 哈夫曼编码Huffman Coding
应用场景
优先队列的作用
4. 合并K个有序链表Merge K Sorted Lists
应用场景
优先队列的作用
5.贪心算法中的应用
应用场景
优先队列的作用
6. 动态中位数维护
应用场景
优先队列的作用
7.石子合并问题Stone Merging Problem
1. 应用场景 最近发现优先队列真的超级好用让我来总结一下激动到起飞.......)。 One What is priority_queue? (什么是优先队列 一堆可以进行比较的数据元素被赋予一定的优先级谁的优先级高先处理谁要是优先级一样高通常按照它们进入队列的顺序进行处理具体取决于代码怎么实现的。 Two The base operation.基础操作
以名称为pq的优先队列简单介绍一下。
1.在c中priority_queue模板类定义在queue头文件中。
2. pq.push(元素); 将一个元素推进pq队列中。
3.pq.top(); 优先队列顶部元素优先级最高的元素。
4.pq.pop;将优先队列最顶部的元素删除,要先取出来pq.top()),再删除。这两步操作要同步进行。
5.pq.size();告诉你这个优先队列有多大 。
6.pq.empty();告诉你这个优先队列是不是空的true表示是空的false表示不空的。 Three Definition methods(定义方式
1.普通版 priority_queuelong long pq;
2.升序版priority_queue元素数据类型盛装元素的容器或数组greatr元素数据类型
举个栗子priorityint,vectorint,greaterint pq;
3.降序版priority_queueint,vectorint,lessint pq;(priority_queue默认降序
4.存储自定义结构体或类时还要搞一个比较器来定义元素的优先级。
存储自定义的方式的5种主要形式
1结构体
默认访问级别公有public这意味着除非明确指定结构体中的成员变量和成员函数都是公有的外部代码可以直接访问它们。
#include iostream
using namespace std;// 使用 struct 定义
struct PointStruct {int x;int y;
};int main(){PointStruct ps;ps.x 10; // 可以直接访问和修改ps.y 20;cout PointStruct: ( ps.x , ps.y )\n;return 0;
}PointStruct: (10, 20)2类
默认访问级别私有private这意味着除非明确指定类中的成员变量和成员函数都是私有的外部代码无法直接访问它们。
#include iostream
#include string
using namespace std;// 使用 class 定义
class PointClass {
private:int x; // 私有成员变量int y; // 私有成员变量public:// 构造函数PointClass(int a 0, int b 0) : x(a), y(b) {}// 公有成员函数设置 x 的值void setX(int a) {x a;}// 公有成员函数设置 y 的值void setY(int b) {y b;}// 公有成员函数获取 x 的值int getX() const {return x;}// 公有成员函数获取 y 的值int getY() const {return y;}// 公有成员函数打印坐标void print() const {cout PointClass: ( x , y )\n;}
};int main(){// 使用 structPointStruct ps;ps.x 10; // 可以直接访问和修改ps.y 20;cout PointStruct: ( ps.x , ps.y )\n;// 使用 classPointClass pc; // 使用默认构造函数// pc.x 30; // 错误x 是私有的无法直接访问// pc.y 40; // 错误y 是私有的无法直接访问// 通过公有成员函数设置值pc.setX(30);pc.setY(40);pc.print();// 通过公有成员函数获取值cout PointClass x: pc.getX() , y: pc.getY() \n;return 0;
}
PointStruct: (10, 20)
PointClass: (30, 40)
PointClass x: 30, y: 40 3类结构体
#include iostream
using namespace std;// 使用struct定义
struct PointStruct {int x;int y;
};// 使用class定义
class PointClass {
public:int x;int y;
};int main(){PointStruct ps;ps.x 10; // 可以直接访问ps.y 20;cout PointStruct: ( ps.x , ps.y )\n;PointClass pc;pc.x 30; // 需要public访问权限pc.y 40;cout PointClass: ( pc.x , pc.y )\n;return 0;
}PointStruct: (10, 20)
PointClass: (30, 40)4使用指针或引用
有时为了节省内存或管理大型数据结构可以在优先队列中存储指针如Node*或引用。
#includebits/stdc.h
using namespace std;// 定义任务结构体
struct Task {int priority;string name;Task(int p, string n) : priority(p), name(n) {}
};// 定义比较器
struct CompareTaskPtr {bool operator()(const Task* a, const Task* b) const {return a-priority b-priority; // 优先级高的先出}
};int main(){// 定义优先队列存储Task*最大堆priority_queueTask*, vectorTask*, CompareTaskPtr pq;// 动态分配任务并插入优先队列pq.push(new Task(3, Task A));pq.push(new Task(1, Task B));pq.push(new Task(4, Task C));pq.push(new Task(2, Task D));// 依次取出任务并释放内存while(!pq.empty()){Task* t pq.top();cout Priority: t-priority , Name: t-name endl;pq.pop();delete t; // 释放动态分配的内存}return 0;
}Priority: 4, Name: Task C
Priority: 3, Name: Task A
Priority: 2, Name: Task D
Priority: 1, Name: Task B5使用枚举类型Enums
当需要基于预定义的优先级级别进行排序时可以使用枚举类型。除了上述常见的struct、class、pair和tuple优先队列还可以存储其他类型的数据具体取决于问题的需求。优先级任务高中低。
#includebits/stdc.h
using namespace std;// 定义优先级枚举
enum Priority { LOW 1, MEDIUM 2, HIGH 3 };// 定义任务结构体
struct Task {Priority priority;string name;Task(Priority p, string n) : priority(p), name(n) {}
};// 定义比较器
struct CompareTask {bool operator()(const Task a, const Task b) const {return a.priority b.priority; // 高优先级先出}
};int main(){// 定义优先队列使用自定义比较器priority_queueTask, vectorTask, CompareTask pq;// 插入任务pq.emplace(HIGH, Task A);pq.emplace(LOW, Task B);pq.emplace(MEDIUM, Task C);pq.emplace(HIGH, Task D);// 依次取出任务while(!pq.empty()){Task t pq.top();cout Priority: t.priority , Name: t.name endl;pq.pop();}return 0;
}Priority: 3, Name: Task A
Priority: 3, Name: Task D
Priority: 2, Name: Task C
Priority: 1, Name: Task B比较器的三种种主要形式 1 重载全局的 operator这种方法会影响所有Node类型的比较不仅限于优先队列。
#includebits/stdc.h
using namespace std;struct Node {int x, y;Node(int a 0, int b 0) : x(a), y(b) {}
};// 重载全局的 operator
bool operator(const Node a, const Node b){if(a.x b.x)return a.y b.y; // y 小的优先return a.x b.x; // x 小的优先
}int main(){// 定义一个存储 Node 的优先队列最大堆priority_queueNode pq;// 插入元素pq.push(Node(5, 3));pq.push(Node(2, 8));pq.push(Node(5, 1));pq.push(Node(3, 7));pq.push(Node(2, 4));pq.push(Node(5, 6));pq.push(Node(1, 9));pq.push(Node(3, 2));pq.push(Node(1, 5));pq.push(Node(4, 0));// 依次取出元素while(!pq.empty()){Node top pq.top();cout top.x top.y endl;pq.pop();}return 0;
}1 5
1 9
2 4
2 8
3 2
3 7
4 0
5 1
5 3
5 62 定义自定义比较器结构体这种方法更具封装性不会影响全局的Node比较仅作用于特定的优先队列。
#include iostream
#include queue
#include vector
using namespace std;struct Node {int x, y;Node(int a 0, int b 0) : x(a), y(b) {}
};// 定义自定义比较器
struct cmp {bool operator()(const Node a, const Node b) const {
//按引用传递为了提高效率比较器的参数最好按const引用传递并将operator()声明为const成员函数。if(a.x b.x)return a.y b.y; // y 小的优先return a.x b.x; // x 小的优先}
};int main(){// 定义一个存储 Node 的优先队列最小堆priority_queueNode, vectorNode, cmp pq;// 插入元素pq.push(Node(5, 3));pq.push(Node(2, 8));pq.push(Node(5, 1));pq.push(Node(3, 7));pq.push(Node(2, 4));pq.push(Node(5, 6));pq.push(Node(1, 9));pq.push(Node(3, 2));pq.push(Node(1, 5));pq.push(Node(4, 0));// 依次取出元素while(!pq.empty()){Node top pq.top();cout top.x top.y endl;pq.pop();}return 0;
}3Lambda 表达式 c及以上版本
#includebits/stdc.h
using namespace std;struct Node {int x, y;Node(int a 0, int b 0) : x(a), y(b) {}
};int main(){// 定义一个存储 Node 的优先队列最小堆使用 Lambda 比较器auto cmp [](const Node a, const Node b) - bool {if(a.x b.x)return a.y b.y; // y 小的优先return a.x b.x; // x 小的优先};priority_queueNode, vectorNode, decltype(cmp) pq(cmp);// 插入元素pq.push(Node(5, 3));pq.push(Node(2, 8));pq.push(Node(5, 1));pq.push(Node(3, 7));pq.push(Node(2, 4));pq.push(Node(5, 6));pq.push(Node(1, 9));pq.push(Node(3, 2));pq.push(Node(1, 5));pq.push(Node(4, 0));// 依次取出元素while(!pq.empty()){Node top pq.top();cout top.x top.y endl;pq.pop();}return 0;
}Priority: 1, Name: Task B
Priority: 2, Name: Task D
Priority: 3, Name: Task A
Priority: 4, Name: Task CFour Application scenario(应用场景
1. 最短路径算法Dijkstra算法
应用场景
问题类型图论中的单源最短路径问题。示例问题给定一个带权有向图计算从起点到所有其他节点的最短路径。
优先队列的作用
在Dijkstra算法中优先队列用于选择当前未处理节点中距离起点最近的节点以确保每次扩展的都是最优路径。
上题目 #includebits/stdc.h
using namespace std;
typedef long long ll;
ll find_min_idx(const ll n,vectorll vis,vectorll dis){ll MINidx-1,MINLLONG_MAX;for(ll i0;in;i){if(dis[i]MIN!vis[i]){MINdis[i];MINidxi;}}return MINidx;
}
void Dijkstra(ll idx,const ll n,vectorll vis,vectorll dis,vectorvectorll mp){dis[idx]0;for(ll i0;in;i){ll ufind_min_idx(n,vis,dis);if(u-1)break;vis[u]1;for(ll j0;jn;j){if(!vis[j]mp[u][j]0mp[u][j]dis[u]dis[j]){dis[j]mp[u][j]dis[u];}}}
}
int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);string s;cins;ll ns.length();vectorvectorll mp(n,vectorll(n,0));for(ll i0;in;i){for(ll j0;jn;j){cinmp[i][j];}}char start;cinstart;ll idxs.find(start);vectorll vis(n,0);vectorll dis(n,LLONG_MAX);dis[idx]0;Dijkstra(idx,n,vis,dis,mp);for(ll i0;in;i){if(iidx)continue;couts[i]: (dis[i]LLONG_MAX?0:dis[i])endl;}return 0;
}
2. 最小生成树算法Prim算法
应用场景
问题类型图论中的最小生成树问题。示例问题给定一个无向带权图找到包含所有节点且边权和最小的树。
优先队列的作用
在Prim算法中优先队列用于选择当前可以连接到生成树的最小权重边。 #includebits/stdc.h
using namespace std;
using u64 unsigned long long;
#define int long long
const int N1e610;
vectorpairint,int e[N],g[N];
int n,m;
int vis[N],dis[N],fa[N];
int ans0,tot2;
void bfs(){priority_queuepairint,int q;q.push({0,1});while(q.size()){auto [d,u] q.top();q.pop();if(vis[u]) continue;vis[u]1;ans-d;for(auto [v,di]:e[u]){q.push({d-di,v});}}
}
void bfs2(){priority_queuepairint,int q;q.push({0,1});while(q.size()){auto [d,u] q.top();q.pop();if(vis[u]tot) continue;vis[u]tot;ans-d;for(auto [v,di]:g[u]){q.push({d-di,v});}}
}
void solve(){cinnm;for(int i1;im;i){int u,v,d;cinuvd;e[u].push_back({v,d});g[v].push_back({u,d});}bfs();bfs2();coutans\n;
}
signed main(){ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);int T1;// cinT;while(T--){solve();}return 0;
} 3. 哈夫曼编码Huffman Coding
应用场景
问题类型数据压缩和编码问题。示例问题根据字符出现频率构建哈夫曼树并生成最优前缀编码。
优先队列的作用
哈夫曼编码算法使用优先队列来选择频率最小的两个节点逐步合并生成哈夫曼树。 #include bits/stdc.h
using namespace std;
typedef long long ll;
struct Node {ll l, r, p, w, id;string res;
};
struct Compare {bool operator()(const Node a, const Node b) const {return a.w ! b.w ? a.w b.w : a.id b.id;}
};
void dfs(vectorNode nodes, ll id, string code) {if (nodes[id].l -1 nodes[id].r -1) {nodes[id].res code; // 直接赋值哈夫曼编码return;}if (nodes[id].l ! -1) dfs(nodes, nodes[id].l, code 0);if (nodes[id].r ! -1) dfs(nodes, nodes[id].r, code 1);
}
int main() {ll n;cin n;string s;cin s;priority_queueNode, vectorNode, Compare pq;vectorNode nodes;for (ll i 0; i n; i) {ll w;cin w;nodes.push_back({-1, -1, -1, w, i, }); // 初始化叶子节点pq.push(nodes.back());}ll nextId n; // 新生成节点的编号从 n 开始while (pq.size() 1) {Node x pq.top();pq.pop();Node y pq.top();pq.pop();Node z {-1, -1, -1, x.w y.w, nextId, };z.l x.id;z.r y.id;nodes[x.id].p z.id;nodes[y.id].p z.id;nodes.push_back(z);pq.push(z);}ll rootId pq.top().id;dfs(nodes, rootId, );for (ll i 0; i n; i) cout nodes[i].res \n;return 0;
}4. 合并K个有序链表Merge K Sorted Lists
应用场景
问题类型链表操作和归并排序。示例问题给定K个有序链表将它们合并为一个有序链表。
优先队列的作用
使用优先队列维护当前K个链表的最小元素逐步合并。 #include bits/stdc.h
using namespace std;
inline uint64_t read() {uint64_t x 0;char ch getchar();while (!isdigit(ch))ch getchar();while (isdigit(ch))x (x 3) (x 1) (ch ^ 48), ch getchar();return x;
}
uint64_t a[10000001], b[10000001];
signed main() {for (int T read(), n, m; (T--) (n read(), m read()); ) {for (int i 1; i n; i)a[i] read();for (int i 1; i m; i)b[i] read();int j 1, cnt 0, ans 0;for (int i 1; i n; i) {cnt 0;while (j m a[i] b[j]) {cnt (a[i] b[j]);j;}ans ^ cnt;}printf(%d\n, ans);}return 0;
} 5.贪心算法中的应用
应用场景
问题类型贪心选择性质的问题如活动安排、区间调度等。示例问题选择尽可能多的不重叠活动。
优先队列的作用
通过优先队列快速选择最优的下一步操作如选择最早结束的活动。 #include bits/stdc.h
#define int long long
using namespace std;
int t,h,n;
struct node{int a,c,now;bool operator (const node b) const{return this-now b.now;}//冷却完成的时间点越早越优先
}b[200005];void solve(){cin h n;int turn 1;for(int i1;in;i) cin b[i].a;for(int i1;in;i) cin b[i].c;queuenode que;priority_queuenode pq;for(int i1;in;i) que.push({b[i].a,b[i].c,1});while(h 0){if(!pq.empty()){turn pq.top().now;while(!pq.empty() pq.top().now turn){que.push({pq.top().a,pq.top().c,pq.top().now});pq.pop();}}while(!que.empty()){h - que.front().a;pq.push({que.front().a,que.front().c,que.front().cque.front().now});que.pop();}}cout turn \n;
}signed main()
{ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);cin t;while(t--){solve();}return 0;
} 6. 动态中位数维护
应用场景
问题类型动态数据流问题需要实时获取中位数。示例问题设计一个数据结构支持动态插入元素并实时获取中位数。
优先队列的作用
使用两个优先队列最大堆和最小堆分别维护较小一半和较大一半的元素以快速计算中位数。
(写的题目没有涉及过以后遇到会补充 7.石子合并问题Stone Merging Problem
1. 应用场景
石子合并问题在多种实际应用中具有重要意义特别是在需要优化合并过程以最小化成本或时间的场景中。通常被归类为**贪心算法Greedy Algorithms**问题因为它涉及在每一步选择最优的局部决策以期达到全局最优的结果。具体类型包括
最小合并成本给定一组石子每次可以合并两个石子合并成本为这两个石子的重量之和目标是通过一系列合并操作使得所有石子最终合并成一个石子并使得总合并成本最小。 #include bits/stdc.h
using namespace std;
typedef long long ll;int main() {ios::sync_with_stdio(false);cin.tie(0);int n;cin n;priority_queueint, vectorint, greaterint pq; for (int i 0; i n; i) {int x;cin x;pq.push(x); }ll total_cost 0; while (pq.size() 1) {int x pq.top();pq.pop();int y pq.top();pq.pop();int merge_cost x y;total_cost merge_cost;pq.push(merge_cost);}cout total_cost endl; return 0;
}
暂时先到这里吧Good Bye!
