问题分析

每个雷达的扫描区域是一个等腰直角三角形，高度为 ( h_i )（( 0 \leq h_i \leq y_i )）时，其覆盖区域的面积为 ( \frac{h_i^2}{2} )，但多个雷达的区域可能重叠，重叠部分的面积不能重复计算。我们需要在最大化总覆盖面积的同时，最小化提升雷达高度的花费，最终求净收入（面积 - 总花费）的最大值。

关键思路

$1$. 单个雷达的贡献：对于雷达 ( i )，若提升高度为 ( h_i )，则其独立贡献的面积为 ( \frac{h_i^2}{2} )，花费为 ( c_i \cdot h_i )。但多个雷达的重叠区域会导致实际面积小于各雷达独立面积之和，因此需要分析雷达间的位置关系，确定哪些区域是重叠的，从而计算有效面积。 2. 区间覆盖与最优高度：将雷达按横坐标排序后，相邻雷达的覆盖区域会形成重叠区间。对于每个雷达，其最优高度受限于自身最大高度 ( y_i ) 和相邻雷达的高度，需通过比较成本和面积增益来确定是否提升高度。

算法设计

$1$. 排序雷达：按横坐标 ( x_i ) 对雷达进行排序，以便分析相邻雷达的覆盖重叠。 2. 计算有效面积：对于每个雷达 ( i )，其有效高度 ( h_i ) 是满足 ( h_i \leq y_i ) 且 ( h_i \leq h_{i-1} + (x_i - x_{i-1}) )、( h_i \leq h_{i+1} + (x_{i+1} - x_i) ) 的最大值（考虑左右相邻雷达的覆盖限制）。 3. 净收入计算：遍历每个雷达，计算其有效高度下的面积贡献（需减去与相邻雷达重叠部分的面积），再减去提升高度的花费，累加得到总净收入。

实现代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;

struct Radar {
    int x, y, c;
};

bool compare(const Radar& a, const Radar& b) {
    return a.x < b.x;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(2);
    
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<Radar> radars(n);
        for (int i = 0; i < n; ++i) {
            cin >> radars[i].x >> radars[i].y >> radars[i].c;
        }
        sort(radars.begin(), radars.end(), compare);
        
        vector<int> h(n, 0);
        // 处理第一个雷达
        h[0] = min(radars[0].y, (n == 1) ? radars[0].y : (radars[1].x - radars[0].x));
        // 处理最后一个雷达
        if (n > 1) {
            h[n-1] = min(radars[n-1].y, radars[n-1].x - radars[n-2].x);
        }
        // 处理中间雷达
        for (int i = 1; i < n-1; ++i) {
            int left = radars[i].x - radars[i-1].x;
            int right = radars[i+1].x - radars[i].x;
            h[i] = min(radars[i].y, min(left, right));
        }
        
        double total_area = 0.0;
        long long total_cost = 0;
        for (int i = 0; i < n; ++i) {
            total_area += (double)h[i] * h[i] / 2.0;
            total_cost += (long long)h[i] * radars[i].c;
        }
        
        // 处理重叠区域的面积（相邻雷达的重叠部分）
        for (int i = 0; i < n-1; ++i) {
            int overlap = h[i] + h[i+1] - (radars[i+1].x - radars[i].x);
            if (overlap > 0) {
                total_area -= (double)overlap * overlap / 2.0;
            }
        }
        
        double net_income = total_area - total_cost;
        cout << net_income << '\n';
    }
    return 0;
}

算法标签

• 贪心算法：每个雷达的最优高度选择是在自身限制和相邻雷达限制下的局部最优，最终构成全局最优。
• 几何分析：通过分析雷达覆盖区域的几何形状（等腰直角三角形）和重叠情况，计算有效覆盖面积。
• 排序与遍历：对雷达按横坐标排序后，线性遍历处理相邻雷达的关系，保证算法效率。

复杂度分析

• 时间复杂度：排序雷达的时间为 ( O(n \log n) )，后续遍历处理的时间为 ( O(n) )，总体时间复杂度为 ( O(n \log n) )，可处理 ( n \leq 10^5 ) 的数据规模。
• 空间复杂度：仅需存储雷达信息和高度数组，空间复杂度为 ( O(n) )。

该算法通过分析雷达覆盖的几何重叠，准确计算有效面积，并结合高度提升的成本，最终得到最大净收入。