首页 > 其他分享 >二分

二分

时间:2024-01-26 17:23:33浏览次数:22  
标签:二分 right return int mid long left

https://www.luogu.com.cn/problem/P8647?contestId=154515
`

include<bits/stdc++.h>

define x first

define y second

using namespace std;
typedef pair<int,int>PII;
const int N=100010;
typedef long long ll;
PII p[N];
int n,k;
int find(int a){
long long sum=0;
int j;
for(j=0;j<n;j++) {
sum += (ll) ((p[j].x / a) * (p[j].y / a)); \判断条件,够分给k为小朋友
}
if(sum>=k){
return 1;
}
else{
return 0;
}
}
int main(){
cin >> n >> k;
int i;
for(i=0;i<n;i++){
cin >> p[i].x >> p[i].y;
}
int left=1;
int right=100000;
while(left<right){
int mid=(left+right+1)/2; \+1
if(find(mid)){
left=mid;
}
else{
right=mid-1; \-1
}
}
cout << left << endl;
return 0;
}
`

标签:二分,right,return,int,mid,long,left
From: https://www.cnblogs.com/CXfang10/p/17989819

相关文章

  • 做题记录(数据结构+整体二分专题)
    情报传递对于每一个操作打上时间戳,对于\(T\)时刻的询问,即为询问路径上比\(T-c\)的值小的数有几个。直接树剖上维护权值树状数组即可。宝石给定一棵树,\(n\)个顶点,每个点有一个宝石,类型为\(W_i\),约定\(W_i\lem\)。你有一个收集器,可以收集至多\(c\)个宝石,并且收集......
  • 代码随想录算法训练营第一天| 704. 二分查找、27. 移除元素。
    704.二分查找题目链接:https://leetcode.cn/problems/binary-search/文章讲解:https://programmercarl.com/0704.二分查找.html简单的二分查找法,核心是认识区间的意义,注意以下几点:middle=low+(low+high)/2;这种写法可以防止溢出。注意low和high的循环条件判断,如果是左闭右闭......
  • CF-431-D-二分+数位DP
    431-D题目大意请你找到一个数\(n\),满足区间\([n+1,2n]\)中恰有\(m\)个数的二进制表示中有\(k\)个\(1\)。Solution这种区间中计数类型的题目首先相当数位DP。但是这里缺乏上下界,难点就在于观察到\(n\)的单调性(\([n+1,2n]\)中有\(k\)个\(1\)的数是单调不减的),简要证明:对于......
  • C# 二分法查询代码
    二分法查找,也称为折半法,是一种在有序数组中查找特定元素的搜索算法。使用二分法的前提条件是:在有序数组中查找特定元素publicstaticintSearchInsert(int[]nums,inttarget){intstart=0;//开始索引intend=nums.Length-1;//结束索引i......
  • 冒泡排序、选择排序、二分查找
    1publicstaticvoidmain(String[]args){2//冒泡排序3//定义一个数组,存储一些数据4int[]arr={5,3,1,2,9,6};5System.out.println("=========冒泡排序==========");6//定义一个循环轮数7fo......
  • CF-91-B-单调栈+二分
    91-B题目大意给定一个长为\(n\)的序列\(a\),对于每个\(a[i]\),你需要找到一个\(j\)满足\(a[i]>a[j]\)且\(j-i\)最大。Solution逆序遍历,维护一个单调递减的栈,如果当前枚举的\(a[i]\)小于栈顶元素,则入栈。如果\(a[i]\)大于栈顶元素,那么后面的元素如果大于\(a[i]\),那么也大于栈顶......
  • 二分查找
    二分查找一、应用场景​ 一个很常见的情景:猜数——猜大了就小一点,猜小了就大一点。我们在这个例子中发现,不停的缩小范围,舍弃(更贴切的说法是“排除”)不必要的搜查范围,这样有利于我们去快速查找。​ 这种二分思想,我们也可应用到其他方面:比如开平方数之类——不停的从目标区间的......
  • 线段树二分
    问题描述维护长度为\(n\)的序列\(a\),支持以下操作:1ix:把\(a_i\)修改为\(x\)。2ix:询问最小的\(j\)满足\(j>=i\)且\(a_j>=x\)。\(1\leqn\leq10^6\)解决方法在线段树外直接二分可以做到\(O(n\log^2n)\)的时间复杂度,加上简单的剪枝可能效率会高一些,但都无......
  • 二分搜索应用 II
    目录1.题目列表2.应用2.1.Leetcode410.分割数组的最大值2.1.1.题目2.1.2.解题思路2.1.3.代码实现1.题目列表序号题目难度1410.分割数组的最大值困难2.应用2.1.Leetcode410.分割数组的最大值2.1.1.题目410.分割数组的最大值给定一个非负整......
  • 【LeetCode】704. 二分查找
    题目:704.二分查找解题思路思路:给定一个nums数组,注意数组是升序排列的;那么,找到当前target元素是否存在于数组之中,可采用二分法查找注意:此处定义该数组区间定义:【左闭右闭】/【左闭右开】使用left指向数组头,right指针指向数组尾,mid用于计算二分查找的位置,mid=left+(ri......