算法打卡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-- > 0) {
              int n = input.nextInt();
              double[] a = new double[n];
  
              for (int i = 0; i < a.length; i++) {//每个喷水装置的初始化
                  a[i] = input.nextDouble();
              }
  
              //采用贪心算法，所以先对每个喷水装置的半径进行排序，从大的开始
              Arrays.sort(a);
  
              int num = 0;
              double sum = 0;
              for (int i = a.length - 1; i >= 0; i--) {
                  if (i > 1) {
                      //计算圆与长方形相交的正方形的面积
                      sum += Math.sqrt(a[i] * a[i] - 1) * 2;
                      num++;
                      if (sum >= 20) {
                          break;
                      }
                  }
              }
              System.out.println(num);
          }
      }
  }
  

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

  

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

  

                                                      长按二维码关注

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