devbox
代码探险家
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

题目练习_第一行读入两个整数m,n。m表示学校数,n表示学生数。 第二行共有m个数,表示m个学校

作者：代码探险家 | 2024-08-18 18:40:57

赞

踩

第一行读入两个整数m,n。m表示学校数,n表示学生数。 第二行共有m个数,表示m个学校

题目：烦恼的高考志愿

题目描述

现有 m 所学校，每所学校预计分数线是 ai​。有 n 位学生，估分分别为 bi​。

根据 n 位学生的估分情况，分别给每位学生推荐一所学校，要求学校的预计分数线和学生的估分相差最小（可高可低，毕竟是估分嘛），这个最小值为不满意度。求所有学生不满意度和的最小值。

输入格式

第一行读入两个整数 m,n。m 表示学校数，n 表示学生数。

第二行共有 m 个数，表示 m 个学校的预计录取分数。第三行有 n 个数，表示 n 个学生的估分成绩。

输出格式

输出一行，为最小的不满度之和。

输入输出样例

输入 #1复制

  1. 4 3
  2. 513 598 567 689
  3. 500 600 550

输出 #1复制

32

说明/提示

数据范围：

对于 30% 的数据，1≤n,m≤1000，估分和录取线 ≤10000；

对于 100% 的数据，1≤n,m≤100000，估分和录取线 ≤1000000 且均为非负整数。

思路：使用了搜索与统计算法

注意：lower_bound 和 upper_bound 返回的是迭代器，它们需要被转换为数组索引才能与 num 进行比较。我之前是这样计算 的abs(p1 - num) 和 abs(p2 - num) ，这是不正确的，因为 p1 和 p2 是索引，而 num 是查询的值。

代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<algorithm>
  4. #include<cstring>
  5. using namespace std;
  6. int n, m, a[6000000], b[6000000];
  7. long long int  num;
  8. int main()
  9. {
  10. 	cin >> m >> n;
  11. 	for (int i = 0; i < m; i++)cin >> a[i];
  12. 	sort(a, a + m);
  13. 	long long int ans = 0;
  14. 	while (n--) {
  15. 		cin >> num;
  16. 		int p1 = lower_bound(a, a + m, num) - a;
  17. 		int p2 = upper_bound(a, a + m, num) - a;
  18. 		if (p1 == m) { // p1指向数组末尾之后的位置  
  19. 			ans += abs(a[m - 1] - num); // 取最后一个元素与num的差的绝对值  
  20. 		}
  21. 		else if (p2 == 0) { // p2指向数组第一个元素之前的位置  
  22. 			ans += abs(a[0] - num); // 取第一个元素与num的差的绝对值  
  23. 		}
  24. 		else {
  25. 			// 计算num与p1和p2指向的元素之间的差的绝对值，并取最小值  
  26. 			int diff1 = abs(a[p1] - num);
  27. 			int diff2 = abs(a[p2 - 1] - num);
  28. 			ans += min(diff1, diff2);
  29. 		}
  30. 	}
  31. 	printf("%lld", ans);
  32. 	return 0;
  33. }

题目：统计方形（数据加强版）

题目描述

有一个 n×m 方格的棋盘，求其方格包含多少正方形、长方形（不包含正方形）。

输入格式

一行，两个正整数 n,m（n≤5000,m≤5000）。

输出格式

一行，两个正整数，分别表示方格包含多少正方形、长方形（不包含正方形）。

输入输出样例

输入 #1复制

2 3

输出 #1复制

8 10

代码： 

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<algorithm>
  4. #include<cstring>
  5. using namespace std;
  6. long long int n, m;
  7. long long int s1, s2, S;
  8. int main()
  9. {
  10. 	cin >> n >> m;
  11. 	for (int i = 1; i <= min(n, m); i++) {
  12. 		s1 += (n - i + 1) * (m - i + 1);
  13. 	}
  14. 	for (int i = 0; i < n; i++) {
  15. 		for (int j = 0; j < m; j++) {
  16. 			if (i != j)s2 += (n - i) * (m - j);
  17. 		}
  18. 	}
  19. 	printf("%lld %lld", s1, s2);
  20. 	return 0;
  21. }

题目：查找文献

题目描述

小 K 喜欢翻看洛谷博客获取知识。每篇文章可能会有若干个（也有可能没有）参考文献的链接指向别的博客文章。小 K 求知欲旺盛，如果他看了某篇文章，那么他一定会去看这篇文章的参考文献（如果他之前已经看过这篇参考文献的话就不用再看它了）。

假设洛谷博客里面一共有 n(n≤10^5) 篇文章（编号为 1 到 n）以及 m(m≤10^6) 条参考文献引用关系。目前小 K 已经打开了编号为 1 的一篇文章，请帮助小 K 设计一种方法，使小 K 可以不重复、不遗漏的看完所有他能看到的文章。

这边是已经整理好的参考文献关系图，其中，文献 X → Y 表示文章 X 有参考文献 Y。不保证编号为 1 的文章没有被其他文章引用。

请对这个图分别进行 DFS 和 BFS，并输出遍历结果。如果有很多篇文章可以参阅，请先看编号较小的那篇(因此你可能需要先排序)。

输入格式

共 1m+1 行，第 1 行为 2 个数，n 和 m，分别表示一共有 n(n≤10^5) 篇文章（编号为 1 到 n）以及m(m≤10^6) 条参考文献引用关系。

接下来 m 行，每行有两个整数 X,Y 表示文章 X 有参考文献 Y。

输出格式

共 2 行。 第一行为 DFS 遍历结果，第二行为 BFS 遍历结果。

输入输出样例

输入 #1复制

  1. 8 9
  2. 1 2
  3. 1 3
  4. 1 4
  5. 2 5
  6. 2 6
  7. 3 7
  8. 4 7
  9. 4 8
  10. 7 8

输出 #1复制

  1. 1 2 5 6 3 7 8 4 
  2. 1 2 3 4 5 6 7 8

代码：

  1. #include<iostream>  
  2. #include<algorithm>  
  3. #include<vector>  
  4. #include<queue>  
  5. using namespace std;
  6.  
  7. // 记录边的结构体  
  8. struct fun {
  9. 	int u; // 起点  
  10. 	int v; // 终点  
  11. };
  12.  
  13. // 存具体信息的二维数组，每个元素是一个向量，用于存储与这个顶点相连的所有边的索引  
  14. vector<int> arr[1000200];
  15.  
  16. // 存边的结构体vector数组  
  17. vector<fun> brr;
  18.  
  19. // 排序规则，如果v相同则按u排序  
  20. bool cmp(fun x, fun y) {
  21. 	if (x.v == y.v) // 这里应该使用双等号进行比较  
  22. 		return x.u < y.u;
  23. 	else
  24. 		return x.v < y.v;
  25. }
  26.  
  27. // 标记是否访问过的数组  
  28. bool vis1[1000200] = { 0 }, vis2[1000200] = { 0 };
  29.  
  30. // DFS函数  
  31. void dfs(int x) {
  32. 	vis1[x] = 1; // 标记为已访问  
  33. 	cout << x << " "; // 输出当前访问的顶点  
  34. 	for (int i = 0; i < arr[x].size(); i++) {// 遍历与x相连的所有边   
  35. 		int p = brr[arr[x][i]].v; // 获取边的终点  
  36. 		if (!vis1[p]) dfs(p); // 如果终点未被访问，则继续DFS  
  37. 	}
  38. }
  39.  
  40. // BFS函数  
  41. void bfs(int x) {
  42. 	queue<int> q; // 创建一个队列用于BFS  
  43. 	q.push(x); // 将起始点加入队列  
  44. 	cout << x << " "; // 输出起始点  
  45. 	vis2[x] = 1; // 标记为已访问  
  46. 	while (!q.empty()) { // 当队列不为空时继续循环    
  47. 		int f = q.front(); // 获取队列的第一个元素  
  48. 		for (int i = 0; i < arr[f].size(); i++) {// 遍历与f相连的所有边    
  49. 			int p = brr[arr[f][i]].v; // 获取边的终点  
  50. 			if (!vis2[p]) {// 如果终点未被访问  
  51. 				q.push(p); // 将终点加入队列  
  52. 				cout << p << " "; // 输出终点  
  53. 				vis2[p] = 1; // 标记为已访问  
  54. 			}
  55. 		}
  56. 		q.pop(); // 弹出队列的第一个元素  
  57. 	}
  58. }
  59.  
  60. int main() {
  61. 	int n, m;
  62. 	cin >> n >> m; // 输入顶点数和边数  
  63. 	for (int i = 0; i < m; i++) {
  64. 		int uu, vv;
  65. 		cin >> uu >> vv; // 输入每条边的起点和终点  
  66. 		brr.push_back({ uu, vv }); // 将边加入brr向量  
  67. 	}
  68. 	sort(brr.begin(), brr.end(), cmp); // 对边按照排序规则进行排序  
  69. 	for (int i = 0; i < m; i++) {
  70. 		arr[brr[i].u].push_back(i); // 根据边的起点，将边的索引添加到对应顶点的向量中
  71.          /*综合起来，arr[brr[i].u].push_back(i); 这行代码的意思是：
  72.          1.  获取 brr 向量中第 i 个元素的 u 成员的值。
  73.          2.  使用这个值作为索引，访问 arr 向量中的对应子向量。
  74.          3.  向这个子向量的末尾添加整数 i。*/  
  75. 	}
  76. 	dfs(1); // 从顶点1开始进行DFS遍历  
  77. 	printf("\n"); // 输出换行  
  78. 	bfs(1); // 从顶点1开始进行BFS遍历  
  79. 	return 0;
  80. }

 题目：最小生成树

题目描述

如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 orz。

输入格式

第一行包含两个整数 N,M，表示该图共有 N 个结点和 M 条无向边。

接下来 M 行每行包含三个整数 Xi​,Yi​,Zi​，表示有一条长度为 Zi​ 的无向边连接结点 Xi​,Yi​。

输出格式

如果该图连通，则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz。

输入输出样例

输入 #1复制

  1. 4 5
  2. 1 2 2
  3. 1 3 2
  4. 1 4 3
  5. 2 3 4
  6. 3 4 3

输出 #1复制

7

说明/提示

数据规模：

对于 20% 的数据，N≤5，M≤20。

对于 40% 的数据，N≤50，M≤2500。

对于 70% 的数据，N≤500，M≤10^4。

对于 100% 的数据：1≤N≤5000，1≤M≤2×10^5，1≤Zi​≤10^4。

样例解释：

所以最小生成树的总边权为 2+2+3=7。

代码：

  1. #include<iostream> // 包含输入输出流库  
  2. #include<cstdio>   // 包含标准输入输出库  
  3. #include<algorithm> // 包含算法库，用于 sort 函数  
  4. #include<cstring>  // 包含字符串处理库，虽然在这段代码中并未使用  
  5. #include<queue>    // 包含队列库，虽然在这段代码中并未使用  
  6.   
  7. using namespace std; // 使用标准命名空间  
  8.   
  9. // 定义一个结构体来存储边的信息  
  10. struct Edge{  
  11. 	int u, v, w; // u 和 v 是边的两个端点，w 是边的权重  
  12. }edge[2000000]; // 存储边的数组，最多可以存储 2000000 条边  
  13.   
  14. int fa[6000], n, m, ans, eu, ev; // fa 是并查集数组，n 是顶点数，m 是边数，ans 是最小生成树的权重和，eu 和 ev 用于存储查找得到的集合代表元素  
  15. int cnt; // 用于计数已选择的边的数量  
  16.   
  17. // 比较函数，用于边的排序  
  18. bool cmp(Edge a, Edge b)  
  19. {  
  20. 	return a.w < b.w; // 按边的权重升序排序  
  21. }  
  22.   
  23. // 查找函数，用于并查集  
  24. int find(int x)   
  25. {  
  26. 	while (x != fa[x]) // 如果 x 不是自己集合的代表元素  
  27. 		x = fa[x] = fa[fa[x]]; // 路径压缩，将 x 直接连接到它的根节点，并返回根节点  
  28. 	return x;  
  29. }  
  30.   
  31. // Kruskal 算法实现函数  
  32. void kruskal()  
  33. {  
  34. 	int b = n - 1; // 最小生成树需要 n - 1 条边  
  35. 	sort(edge, edge + m, cmp); // 对边按权重进行排序  
  36. 	for (int i = 0; i < m; i++) { // 遍历每条边  
  37. 		eu = find(edge[i].u), ev = find(edge[i].v); // 查找边的两个端点所在集合的代表元素  
  38. 		if (eu == ev) continue; // 如果两个端点已经在同一个集合中（即已经连通），则跳过这条边  
  39. 		ans += edge[i].w; // 累加这条边的权重到最小生成树的权重和中  
  40. 		fa[ev] = eu; // 合并两个集合  
  41. 		cnt++; // 已选择的边数加1  
  42. 		if (cnt == b) break; // 如果已选择的边数达到 n - 1，则最小生成树构建完成，退出循环  
  43. 	}  
  44. 	if (cnt < b) { // 如果选择的边数少于 n - 1  
  45. 		cout << "orz" << endl; // 输出"orz"表示图不连通  
  46. 		ans = 0; // 重置最小生成树权重和为0  
  47. 		return; // 返回，不再执行后续代码  
  48. 	}  
  49. }  
  50.   
  51. int main()  
  52. {  
  53. 	cin >> n >> m; // 读入顶点数和边数  
  54. 	for (int i = 1; i <= n; i++) fa[i] = i; // 初始化并查集，每个顶点自成一个集合  
  55. 	for (int i = 0; i < m; i++) { // 读入每条边的信息  
  56. 		cin >> edge[i].u >> edge[i].v >> edge[i].w;  
  57. 	}  
  58. 	kruskal(); // 调用 Kruskal 算法函数构建最小生成树  
  59. 	if(ans != 0) // 如果最小生成树权重和不为0（即图连通）  
  60. 		printf("%d", ans); // 输出最小生成树权重和  
  61. 	return 0; // 程序结束  
  62. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/代码探险家/article/detail/998649
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号