【二分】BISHI86 圆覆盖

思路

求解代码

/** * 表示一个点的静态内部类 * 包含两个属性：d2和v */staticclassPoint{// 平方距离属性，通常用于表示点与点之间的距离平方longd2;// 权值属性longv;Point(longd2,longv){// 使用this关键字将参数值赋给类的成员变量this.d2=d2;this.v=v;}}publicstaticvoidmain(String[]args)throwsIOException{// 使用BufferedReader读取输入，使用PrintWriter输出结果BufferedReaderbr=newBufferedReader(newInputStreamReader(System.in));PrintWriterout=newPrintWriter(newOutputStreamWriter(System.out));// 读取第一行输入，分割为字符串数组String[]strA=br.readLine().trim().split("\\s+");// 获取点的数量nintn=Integer.parseInt(strA[0]);// 获取所需的最小权值SlongS=Long.parseLong(strA[1]);// 创建二维数组存储每个点的坐标和权值long[][]a=newlong[n][3];// 创建Point数组，用于存储每个点到原点的距离平方和权值Point[]points=newPoint[n];// 初始化总权值longtotal=0;// 读取每个点的数据并计算相关信息for(inti=0;i<n;i++){// 读取一行输入并分割String[]str=br.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]);// 累加总权值total+=a[i][2];}// 如果总权值小于所需权值S，输出-1并返回if(total<S){out.println("-1");out.flush();return;}// 对points数组进行排序，使用Lambda表达式作为比较器，按照d2属性值升序排序Arrays.sort(points,(x1,x2)->Long.compare(x1.d2,x2.d2));// 创建前缀和数组preSum，长度为nlong[]preSum=newlong[n];// 初始化前缀和数组的第一个元素为points[0]的v值preSum[0]=points[0].v;// 计算前缀和数组，preSum[i]存储从points[0]到points[i]的v值之和for(inti=1;i<n;i++){preSum[i]=preSum[i-1]+points[i].v;}// 初始化二分查找的边界，low为0，high为n-1intlow=0,high=n-1;// 初始化index为n-1，用于存储满足条件的最小索引intindex=n-1;// 使用二分查找算法找到满足preSum[mid] >= S的最小mid值while(low<=high){// 计算中间位置，使用位运算防止溢出intmid=low+((high-low)>>1);// 如果当前前缀和大于等于S，则更新index并向左查找更小的值if(preSum[mid]>=S){index=mid;high=mid-1;}else{// 否则向右查找low=mid+1;}}// 输出满足条件的点的d2值的平方根out.println(Math.sqrt(points[index].d2));// 刷新输出流out.flush();// 关闭输出流out.close();// 关闭输入流br.close();}