算法打卡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

思路：

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容量（低门槛付费群），长按二维码入群

                                                    长按二维码关注