救援算法：优化救援时间

问题描述：

救生船从大本营出发，营救若干屋顶上的人回到大本营，屋顶数目以及每个屋顶的坐标和人数都将由输入决定，求出所有人都到达大本营并登陆所用的时间。

假设：

在直角坐标系的原点是大本营，救生船每次从大本营出发，救了人之后将人送回大本营。
坐标系中的点代表屋顶，每个屋顶由其位置坐标和其上的人数表示。
救生船每次从大本营出发，以速度50 米/分钟驶向下一个屋顶，达到一个屋顶后，救下其上的所有人，每人上船1分钟，船原路返回，达到大本营，每人下船0.5分钟。
假设原点与任意一个屋顶的连线不穿过其它屋顶。

输入描述：

第一行，一个整数，表示屋顶数n。接下来依次有n 行输入，每一行上包含两个表示屋顶相对于大本营的平面坐标位置的实数(单位是米)、一个表示人数的整数。

输出描述：

救援需要的总时间，精确到分钟(向上取整)。

算法思路：

首先计算每个屋顶到大本营的距离，即屋顶的坐标与原点的欧几里得距离。
将所有屋顶按照距离从小到大进行排序。
从最近的屋顶开始救援，计算救援该屋顶上的人所需的时间。
救援完成后，返回大本营，计算返回大本营所需的时间。
将救援每个屋顶的时间累加，得到总时间。

代码实现：

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>

using namespace std;

struct Rooftop {
    double x;
    double y;
    int people;
    double distance;
};

bool cmp(const Rooftop& a, const Rooftop& b) {
    return a.distance < b.distance;
}

int main() {
    int n;
    cin >> n;
    
    vector<Rooftop> rooftops(n);
    
    for (int i = 0; i < n; i++) {
        cin >> rooftops[i].x >> rooftops[i].y >> rooftops[i].people;
        rooftops[i].distance = sqrt(rooftops[i].x * rooftops[i].x + rooftops[i].y * rooftops[i].y);
    }
    
    sort(rooftops.begin(), rooftops.end(), cmp);
    
    double total_time = 0.0;
    double cur_x = 0.0;
    double cur_y = 0.0;
    
    for (int i = 0; i < n; i++) {
        double distance = sqrt((rooftops[i].x - cur_x) * (rooftops[i].x - cur_x) + (rooftops[i].y - cur_y) * (rooftops[i].y - cur_y));
        double rescue_time = distance / 50.0;
        double people_time = rooftops[i].people;
        
        total_time += rescue_time + people_time;
        
        cur_x = rooftops[i].x;
        cur_y = rooftops[i].y;
    }
    
    double return_time = sqrt(cur_x * cur_x + cur_y * cur_y) / 50.0;
    
    total_time += return_time;
    
    cout << fixed << setprecision(0) << ceil(total_time) << endl;
    
    return 0;
}

复杂度分析：

排序的时间复杂度为O(nlogn)，遍历结构体数组的时间复杂度为O(n)，因此总的时间复杂度为O(nlogn)。
空间复杂度为O(n)，存储结构体数组需要O(n)的额外空间。

优化方向：

可以使用更快的排序算法，例如快速排序或归并排序。
可以使用更有效的距离计算方法，例如使用曼哈顿距离或切比雪夫距离。
可以使用动态规划算法，以求解最优路径。

结论：

本算法通过贪婪策略，实现了对救援时间的优化。算法的时间复杂度为O(nlogn)，空间复杂度为O(n)，可以满足大多数救援场景的需求。可以通过进一步的优化，提高算法的效率和准确性。