【二分】BISHI86 圆覆盖

思路求解代码/** * 表示一个点的静态内部类 * 包含两个属性d2和v */staticclassPoint{// 平方距离属性通常用于表示点与点之间的距离平方longd2;// 权值属性longv;Point(longd2,longv){// 使用this关键字将参数值赋给类的成员变量this.d2d2;this.vv;}}publicstaticvoidmain(String[]args)throwsIOException{// 使用BufferedReader读取输入使用PrintWriter输出结果BufferedReaderbrnewBufferedReader(newInputStreamReader(System.in));PrintWriteroutnewPrintWriter(newOutputStreamWriter(System.out));// 读取第一行输入分割为字符串数组String[]strAbr.readLine().trim().split(\\s);// 获取点的数量nintnInteger.parseInt(strA[0]);// 获取所需的最小权值SlongSLong.parseLong(strA[1]);// 创建二维数组存储每个点的坐标和权值long[][]anewlong[n][3];// 创建Point数组用于存储每个点到原点的距离平方和权值Point[]pointsnewPoint[n];// 初始化总权值longtotal0;// 读取每个点的数据并计算相关信息for(inti0;in;i){// 读取一行输入并分割String[]strbr.readLine().trim().split(\\s);// 存储x坐标a[i][0]Long.parseLong(str[0]);// 存储y坐标a[i][1]Long.parseLong(str[1]);// 存储权值a[i][2]Long.parseLong(str[2]);// 创建Point对象计算点到原点的距离平方points[i]newPoint(a[i][0]*a[i][0]a[i][1]*a[i][1],a[i][2]);// 累加总权值totala[i][2];}// 如果总权值小于所需权值S输出-1并返回if(totalS){out.println(-1);out.flush();return;}// 对points数组进行排序使用Lambda表达式作为比较器按照d2属性值升序排序Arrays.sort(points,(x1,x2)-Long.compare(x1.d2,x2.d2));// 创建前缀和数组preSum长度为nlong[]preSumnewlong[n];// 初始化前缀和数组的第一个元素为points[0]的v值preSum[0]points[0].v;// 计算前缀和数组preSum[i]存储从points[0]到points[i]的v值之和for(inti1;in;i){preSum[i]preSum[i-1]points[i].v;}// 初始化二分查找的边界low为0high为n-1intlow0,highn-1;// 初始化index为n-1用于存储满足条件的最小索引intindexn-1;// 使用二分查找算法找到满足preSum[mid] S的最小mid值while(lowhigh){// 计算中间位置使用位运算防止溢出intmidlow((high-low)1);// 如果当前前缀和大于等于S则更新index并向左查找更小的值if(preSum[mid]S){indexmid;highmid-1;}else{// 否则向右查找lowmid1;}}// 输出满足条件的点的d2值的平方根out.println(Math.sqrt(points[index].d2));// 刷新输出流out.flush();// 关闭输出流out.close();// 关闭输入流br.close();}