ans

liujunhao 2023-12-02 11:18:56 6 返回题目

#include #include #include #include

using namespace std;

struct Sprinkler { double start, end; };

bool compare(const Sprinkler& a, const Sprinkler& b) { return a.start < b.start; }

int main() { int test_cases; cin >> test_cases;

while (test_cases--) {
    int n, L, W;
    cin >> n >> L >> W;
    vector<Sprinkler> sprinklers;
    for (int i = 0; i < n; i++) {
        double pos, r;
        cin >> pos >> r;
        // 只有当喷头半径大于草坪宽度的一半时,才能覆盖草坪
        if (r >= W / 2.0) {
            double dx = sqrt(r * r - W * W / 4.0);
            sprinklers.push_back({pos - dx, pos + dx});
        }
    }

    // 根据起始点排序
    sort(sprinklers.begin(), sprinklers.end(), compare);

    // 使用贪心算法选择喷头
    int count = 0;
    double currentEnd = 0;
    for (int i = 0; i < sprinklers.size() && currentEnd < L;) {
        double furthestEnd = currentEnd;
        bool found = false;
        while (i < sprinklers.size() && sprinklers[i].start <= currentEnd) {
            if (sprinklers[i].end > furthestEnd) {
                furthestEnd = sprinklers[i].end;
                found = true;
            }
            i++;
        }
        if (!found) break; // 没有找到可用的喷头
        currentEnd = furthestEnd;
        count++;
    }

    if (currentEnd < L) {
        cout << -1 << endl; // 无法覆盖整个草坪
    } else {
        cout << count << endl; // 打印最小需要的喷头数量
    }
}

return 0;

}

{{ vote && vote.total.up }}