算法打卡39——喷水装置

本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer,已开源在github ,欢迎star!

转载声明:转载请注明出处,本技术博客是本人原创文章

本文GitHub https://github.com/OUYANGSIHAI/JavaInterview 已收录,这是我花了6个月总结的一线大厂Java面试总结,本人已拿大厂offer,欢迎star

原文链接:blog.ouyangsihai.cn >> 算法打卡39——喷水装置

365算法每日学计划

39打卡:

  • 描述- 现有一块草坪,长为20米,宽为2米,要在横中心线上放置半径为Ri的喷水装置,每个喷水装置的效果都会让以它为中心的半径为实数Ri(0<ri<15)的圆被湿润,这有充足的喷水装置i(1<i<600)个,并且一定能把草坪全部湿润,你要做的是:选择尽量少的喷水装置,把整个草坪的全部湿润。< p=””>-
    • 输入- 第一行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
    • 
      2
      5
      

    思路:

    
    import java.util.Arrays;
    import java.util.Scanner;
    
    public class _39 {
    
        public static void main(String[] args) {
    
            Scanner input = new Scanner(System.in);
            int m = input.nextInt();
    
            while (m-- &gt; 0) {
                int n = input.nextInt();
                double[] a = new double[n];
    
                for (int i = 0; i &lt; a.length; i++) {//每个喷水装置的初始化
                    a[i] = input.nextDouble();
                }
    
                //采用贪心算法,所以先对每个喷水装置的半径进行排序,从大的开始
                Arrays.sort(a);
    
                int num = 0;
                double sum = 0;
                for (int i = a.length - 1; i &gt;= 0; i--) {
                    if (i &gt; 1) {
                        //计算圆与长方形相交的正方形的面积
                        sum += Math.sqrt(a[i] * a[i] - 1) * 2;
                        num++;
                        if (sum &gt;= 20) {
                            break;
                        }
                    }
                }
                System.out.println(num);
            }
        }
    }
    

    注:思海同学创建了一个算法每日学交流社区,如果有想加入的小伙伴,可以扫一下下面的二维码加我为好友,我拉你入群(请备注:算法)。

    附上热门QQ群,存放资源和历史资料,2000容量(低门槛付费群),长按二维码入群

                                                        长按二维码关注

    原文地址:https://sihai.blog.csdn.net/article/details/109464831

本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer,已开源在github ,欢迎star!

转载声明:转载请注明出处,本技术博客是本人原创文章

本文GitHub https://github.com/OUYANGSIHAI/JavaInterview 已收录,这是我花了6个月总结的一线大厂Java面试总结,本人已拿大厂offer,欢迎star

原文链接:blog.ouyangsihai.cn >> 算法打卡39——喷水装置


 上一篇
java web总结——servlet java web总结——servlet
一,Servlet 简介Java Servlet 是运行在 Web 服务器或应用服务器上的程序,它是作为来自 Web 浏览器或其他 HTTP 客户端的请求和 HTTP 服务器上的数据库或应用程序之间的中间层。 使用 Servlet,您可以收
2021-04-04
下一篇 
Oracle12g添加c##scott用户 Oracle12g添加c##scott用户
1.前言在Oracle12c中,已经没有了scott这一实例用户。Oracle学习者们可以通过新建hr用户或是新建scott用户,来完成对Oracle的学习。 2.具体流程登录系统用户 conn / as sysdba; 删除已有的用
2021-04-04