救援 - C++ 解题思路及代码实现

{"title":"救援","description":"救生船从大本营出发，营救若干屋顶上的人回到大本营，屋顶数目以及每个屋顶的坐标和人数都将由输入决定，求出所有人都到达大本营并登陆所用的时间。\n\n在直角坐标系的原点是大本营，救生船每次从大本营出发，救了人之后将人送回大本营。坐标系中的点代表屋顶，每个屋顶由其位置坐标和其上的人数表示。救生船每次从大本营出发，以速度50 米/分钟驶向下一个屋顶，达到一个屋顶后，救下其上的所有人，每人上船1分钟，船原路返回，达到大本营，每人下船0.5分钟。假设原点与任意一个屋顶的连线不穿过其它屋顶。","keywords":"救援, 算法, C++, 代码, 解题思路","content":"解题思路：\n\n1. 首先，读取输入的屋顶数量n。\n2. 创建一个空的集合，用于存储每个屋顶的坐标和人数。\n3. 使用一个循环，从1到n，读取每个屋顶的坐标和人数，并将其添加到集合中。\n4. 创建一个变量total_time，用于存储总的救援时间。\n5. 创建一个变量current_pos，用于存储当前救生船的位置，初始为大本营的坐标(0, 0)。\n6. 使用一个循环，从1到n，遍历集合中的每个屋顶。\n7. 计算当前救生船从大本营到当前屋顶的距离，即当前屋顶的坐标减去当前位置的坐标。\n8. 计算救援当前屋顶上的人所需要的时间，即人数乘以1分钟。\n9. 计算救生船返回大本营所需要的时间，即当前屋顶的坐标减去当前位置的坐标再除以速度50。\n10. 更新当前位置为当前屋顶的坐标。\n11. 将救援当前屋顶所需的时间加到总的救援时间上。\n12. 输出总的救援时间，向上取整。\n\nC++代码实现：\n\ncpp\n#include <iostream>\n#include <vector>\n#include <cmath>\n#include <algorithm>\nusing namespace std;\n\nint main() {\n int n;\n cin >> n;\n \n vector<pair<double, pair<double, int>>> roofs;\n for (int i = 0; i < n; i++) {\n double x, y;\n int people;\n cin >> x >> y >> people;\n roofs.push_back({sqrt(x*x + y*y), {x, people}});\n }\n \n sort(roofs.begin(), roofs.end());\n \n double total_time = 0;\n pair<double, double> current_pos = {0, 0};\n \n for (int i = 0; i < n; i++) {\n double distance = roofs[i].first;\n int people = roofs[i].second.second;\n double rescue_time = people * 1.0;\n double return_time = distance / 50.0;\n \n current_pos = roofs[i].second;\n \n total_time += rescue_time + return_time;\n }\n \n cout << ceil(total_time) << endl;\n \n return 0;\n}\n\n\n时间复杂度分析：\n\n该算法的时间复杂度为O(nlogn)，其中n为屋顶的数量。主要消耗时间的是对屋顶的排序操作，其时间复杂度为O(nlogn)。其余操作的时间复杂度为O(n)，可以忽略不计。