记录编号	570911	评测结果	AAAAAA
题目名称	喷水装置	最终得分	100
用户昵称	惠惠	是否通过	通过
代码语言	C++	运行时间	0.214 s
提交时间	2022-04-25 21:46:58	内存使用	3.04 MiB

#include <bits/stdc++.h>
using namespace std;
    
int T;
    
struct Sprinkler    //给喷水装置存为结构体，包含勾股定理后的喷水范围，装置位置，喷水半径
{
    double range, x, r;
}sprinkler[15010];

struct Suitable     //给精华使用（见下文）
{
    int xiabiao;
    double right;
};
    
bool cmp(const Sprinkler& a, const Sprinkler& b)    //cmp函数给sort排序使用（根据位置从左往右排序）
{
    if(a.x < b.x) return true;
    else return false;
}

bool cmp2(const Suitable& a, const Suitable& b)     //cmp2函数给sort排序使用（根据能覆盖范围的最右侧从大往小排）
{
    if(a.right > b.right) return true;
    else return false;
}

int main()
{
    freopen("sprinkler.in","r",stdin);
    freopen("sprinkler.out","w",stdout);
    cin >> T;
    for(int group = 1; group <= T; ++group)     //循环T组
    {
        int n, spr_cnt = 0, ans = 0;    //定义：喷水装置总数，有效喷水装置数，最终答案数
        double L, W;
        cin >> n >> L >> W;     //输入
        for(int i = 1; i <= n; ++i)     //循环n次，输入有效喷水装置，无效装置（半径小于W/2）直接舍去
        {
            double x, r;
            cin >> x >> r;
            if(r > W / 2)
            {
                ++spr_cnt;
                sprinkler[spr_cnt].r = r;
                sprinkler[spr_cnt].x = x;
            }
        }
        sort(sprinkler + 1, sprinkler + spr_cnt + 1, cmp);      //根据位置从左往右排序
        for(int i = 1; i <= spr_cnt; ++i)       //求出并存贮每个有效装置使用勾股定理求出的喷水范围
        {
            sprinkler[i].range = sqrt(sprinkler[i].r * sprinkler[i].r - (W / 2) * (W / 2));
        }
        int start = 0;      //定义：当前被选取装置中最右边的装置的下标（目前没有选取任何装置，故为0）
        for(int i = spr_cnt; i >= 1; --i)       //从右向左，找能覆盖到草最左边的 最靠右的装置
        {
            if(sprinkler[i].range >= sprinkler[i].x)
            {
                start = i;
                ++ans;
                break;
            }
        }
        if(start == 0)      //如果未找到能覆盖到草地左边的装置，本组无解，输出-1
        {
            cout << -1 << endl;
            continue;
        }
        double left = sprinkler[start].x + sprinkler[start].range;      //定义：当前被覆盖范围的最右边
        if(left >= L)       //如果第一个装置已覆盖全部草地，直接输出1，并结束本组，开始下一组
        {
            cout << ans << endl;
            continue;
        }
        /*精华，关键，重点，万恶之源*/
        /*时间复杂度n(O^2)*/
        for(int i = start + 1; i < spr_cnt; )       //从被选中装置中最右边的装置遍历
        {
            Suitable suit_spr[spr_cnt - start + 1];     //建立结构体，存储候选装置的下标（xiabiao）和能覆盖范围的最右侧（righ）
            int cnt = 0;        //候选装置数量
            for(int j = i; j <= spr_cnt; ++j)       //开始遍历
            {
                if(sprinkler[j].x - sprinkler[j].range <= left)     //如果遍历到的装置可以覆盖到已覆盖范围的最右侧，将该装置加入候选
                {
                    ++cnt;      //候选装置数+1
                    suit_spr[cnt].xiabiao = j;
                    suit_spr[cnt].right = sprinkler[j].x + sprinkler[j].range;
                }
            }       //遍历结束
            if(cnt == 0) break;     //如果无候选装置，结束遍历
            if(cnt > 1) sort(suit_spr + 1, suit_spr + cnt + 1, cmp2);       //如果候选装置不止一个，排序，选出覆盖范围最靠右的装置
            left = suit_spr[1].right;       //更新覆盖范围的最右侧为最靠右的装置的范围
            i = suit_spr[1].xiabiao + 1;    //下次遍历从候选装置中范围最靠右的装置的下一个开始遍历
            ++ans;      //答案数+1
            if(left >= L)
            {
                cout << ans << endl;      //如果该装置可以覆盖草地最右边，则直接输出答案数
                break;
            }
        }
        if(left < L) cout << -1 << endl;      //若最右边的装置无法覆盖到草地最右侧，则无解，输出-1
    }
    return 0;
}