喷水装置（一）（贪心）

朴灿烈づ我的快乐病毒、 2022-07-10 12:00 206阅读 0赞

## 喷水装置（一） ##

时间限制： 3000 ms  |  内存限制： 65535 KB

难度： 3

描述

现有一块草坪，长为20米，宽为2米，要在横中心线上放置半径为Ri的喷水装置，每个喷水装置的效果都会让以它为中心的半径为实数Ri(0<Ri<15)的圆被湿润，这有充足的喷水装置i（1<i<600)个，并且一定能把草坪全部湿润，你要做的是：选择尽量少的喷水装置，把整个草坪的全部湿润。

输入

第一行m表示有m组测试数据  
每一组测试数据的第一行有一个整数数n，n表示共有n个喷水装置，随后的一行，有n个实数ri，ri表示该喷水装置能覆盖的圆的半径。

输出

输出所用装置的个数

样例输入

2
    5
    2 3.2 4 4.5 6 
    10
    1 2 3 1 2 1.2 3 1.1 1 2

样例输出

2
    5

#include <bits/stdc++.h>
    
    using namespace std;
    
    const int maxn = 605;
    double vis[maxn];
    bool cmp(double a,double b)
    {
        return a>b;
    }
    int main()
    {
        int m;
        cin>>m;
        while(m--)
        {
            int n;
            cin>>n;
            for(int i=0;i<n;i++)
                cin>>vis[i];
            sort(vis,vis+n,cmp);
            double length = 0;
            for(int i=0;i<n;i++)
            {
                length += 2*sqrt(vis[i] * vis[i] -1);
                if(length >=20)
                {
                    cout<<i+1<<endl;
                    break;
                }
            }
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，206人围观）

还没有评论，来说两句吧...

相关阅读

相关 nyoj 题目6 喷水装置（贪心）

喷水装置（一）时间限制： 3000 ms | 内存限制： 65535 KB 难度： 3 描述现有一块草坪，长为20米，宽为2米，要在横中心线上放置半径为Ri的喷

蔚落/ 2024年02月18日 16:34/ 0 赞/ 43 阅读

相关题目6 喷水装置（一）

![20160728104130350][] 已AC代码： include<cstdio> include<algorithm> using nam

女爷i/ 2022年09月24日 08:28/ 0 赞/ 151 阅读

相关 NYOJ 6 喷水装置（一）

喷水装置（一）时间限制： 3000 ms | 内存限制： 65535 KB 难度： 3 描述现有一块草坪，长为20米，宽为2米，要在横中心线上放置半径为Ri的喷

旧城等待，/ 2022年08月25日 01:49/ 0 赞/ 151 阅读

相关喷水装置（一）

描述现有一块草坪，长为20米，宽为2米，要在横中心线上放置半径为Ri的喷水装置，每个喷水装置的效果都会让以它为中心的半径为实数Ri(0<Ri<15)的圆被湿润，这有充足的喷

清疚/ 2022年08月11日 16:55/ 0 赞/ 156 阅读

相关喷水装置（二）

喷水装置（二）时间限制： 3000 ms | 内存限制： 65535 KB 难度： 4 描述有一块草坪，横向长w,纵向长为h,在它的橫向中心线上不同位置处装

阳光穿透心脏的1/2处/ 2022年07月12日 13:53/ 0 赞/ 179 阅读

相关喷水装置（一）（贪心）

喷水装置（一）时间限制： 3000 ms | 内存限制： 65535 KB 难度： 3 描述现有一块草坪，长为20米，宽为2米，要在横中心线上放置半径为Ri

朴灿烈づ我的快乐病毒、/ 2022年07月10日 12:00/ 0 赞/ 207 阅读

相关 acm练习：喷水装置(一)

喷水装置（一）时间限制：3000 ms | 内存限制：65535 KB 难度：3 描述现有一块草坪，长为20米，宽为2米，要在横中心线上放置半径为Ri的喷

红太狼/ 2022年06月10日 06:51/ 0 赞/ 167 阅读

相关 C语言贪心算法之喷水装置（二）

喷水装置（二）时间限制：3000 ms | 内存限制：65535 KB 难度：4 描述有一块草坪，横向长w,纵向长为h,在它的橫向中心线上不同位置处装有n(

ゞ浴缸里的玫瑰/ 2022年06月04日 06:41/ 0 赞/ 209 阅读

相关 NYOJ 12 喷水装置（二）——————贪心，区间覆盖

喷水装置（二）时间限制：3000 ms | 内存限制：65535 KB 难度：4 描述有一块草坪，横向长w,纵向长为h,在它的橫向中心线上不同位置处装有n

ゞ浴缸里的玫瑰/ 2022年05月11日 12:12/ 0 赞/ 197 阅读

相关 acm 喷水装置（一）

喷水装置（一）时间限制：3000 ms | 内存限制：65535 KB 难度：3 输入第一行m表示有m组测试数据每一组测试数据的第一行有一个整数数n，

小咪咪/ 2022年05月11日 11:52/ 0 赞/ 184 阅读