记录编号	570894	评测结果	AAAAAA
题目名称	喷水装置	最终得分	100
用户昵称	惠惠	是否通过	通过
代码语言	C++	运行时间	0.232 s
提交时间	2022-04-25 21:08:39	内存使用	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)
{
    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)
        {
            cout << ans << endl;
            continue;
        }
        for(int i = start + 1; i < spr_cnt; )
        {
            Suitable suit_spr[spr_cnt - start + 1];
            int cnt = 0;
            for(int j = i; j <= spr_cnt; ++j)
            {
                if(sprinkler[j].x - sprinkler[j].range <= left)
                {
                    ++cnt;
                    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;
            if(left >= L)
            {
                cout << ans << endl;      //如果最后的装置可以覆盖草地最右边，则输出答案数
                break;
            }
        }
        // for(int i = spr_cnt; i > start; )       //从右向左，找能覆盖 当前覆盖范围最右边 的装置，并更新覆盖范围
        // {
        //     if(sprinkler[i].x - sprinkler[i].range <= left)     //找到符合上述条件的装置
        //     {
        //         left = sprinkler[i].x + sprinkler[i].range;     //更新覆盖范围
        //         start = i;      //更新被选取装置中最右边的装置
        //         i = spr_cnt;    //重新从最右边开始寻找
        //         ++ans;          //答案数+1
        //         continue;
        //     }
        //     --i;        //若本装置不能覆盖当前范围的最右边，则找下一个
        // }  
        if(left < L) cout << -1 << endl;      //若不能，则无解，输出-1
    }
    return 0;
}