首页 > 其他分享 >二分查找法理解

二分查找法理解

时间:2024-01-27 10:33:07浏览次数:35  
标签:二分 vector int 理解 合金 找到 查找


最开始做这道题的时候没想到用这种方法,我之后也在想二分查找法什么时候能用。
其本质上还是在有序的范围中找到目标的数。这道题也就是要找到最大的合金数。
最基本的二分查找题目就是找到具体的那个数,等不等于那个数就是作为限制条件。
那这一题呢就是花费要小于限定值。
因此不断遍历每个机器找到所需花费,如果找到一个机器在目前合金数下能实现(就是小于花费的限定值)。就直接返回,因为求的就是合金数,能找到一种情况直接返回就行了。
具体代码:

点击查看代码
class Solution {
public:
    int maxNumberOfAlloys(int n, int k, int budget, vector<vector<int>>& composition, vector<int>& stock, vector<int>& cost) {
        int left=0;int right=2e8;int mid=0;int ans=0;
        while(left<=right){
              bool flag=false;
            mid=(left+right)/2;          
            for(int i=0;i<composition.size();i++){
                long long spend=0;
                for(int j=0;j<composition[i].size();j++){
spend += max(static_cast<long long>(composition[i][j]) * mid - stock[j], 0LL) * cost[j];

}
if(spend<=budget){
    flag=true;
    break;
}
                }
if(flag){
    ans=mid;
    left=mid+1;
}
            else{
right=mid-1;
            }
        }
        return ans;
    }
};

标签:二分,vector,int,理解,合金,找到,查找
From: https://www.cnblogs.com/yun-che/p/17991170

相关文章

  • 深入理解ZooKeeper分布式锁
    第1章:引言分布式系统,简单来说,就是由多台计算机通过网络相连,共同完成任务的系统。想象一下,咱们平时上网浏览网页、看视频,背后其实都是一大堆服务器在协同工作。这些服务器之间需要协调一致,保证数据的一致性和完整性,这就是分布式系统的挑战之一。在这种环境下,锁就显得尤为重要了......
  • 【学习笔记】二分图的边染色
    定义首先定义无向图的边着色。对无向图\(G\)的边着色,要求相邻的边涂不同种颜色。若\(G\)是\(k\)-边可着色的,但不是\(\left(k-1\right)\)-边可着色的,则称\(k\)是\(G\)的边色数。记为\(\chi^{\prime}\left(G\right)\)。Vizing定理若\(G\)是简单图,那么有......
  • Leetcode刷题第四天-双指针-二分法
    15:三个数之和链接:15.三数之和-力扣(LeetCode)em...双冲for循环,从头去遍历,0-(a+b)是否在列表中,最终timeout数组从小到大排序,设置三个指针,i从头遍历到lens-1,j从i+1开始,k从lens-1开始,sums==0,放入结果,大于0,k-1,小于0,j+1如果i和i+1比较,相同跳过的话,会丢结果,i和i-1相等跳过,因为i-1已......
  • 二分
    https://www.luogu.com.cn/problem/P8647?contestId=154515`include<bits/stdc++.h>definexfirstdefineysecondusingnamespacestd;typedefpair<int,int>PII;constintN=100010;typedeflonglongll;PIIp[N];intn,k;intfind(inta){longl......
  • C++ RALL机制理解
    #########################RALL机制(将资源的生命周期与对象的生命周期所绑定(构造获取资源/析构释放资源,利用了栈上的变量在离开作用域的时候会析构的特性)RAII的做法是使用一个对象,在其构造时获取对应的资源,在对象生命期内控制对资源的访问,使之始终保持有效,最后在对象析构的时候,......
  • 人人看得懂的ChatGPT技术原理解析
    人人看得懂的ChatGPT技术原理解析编者按:自ChatGPT面世以来,我们在热切挖掘其丰富应用的同时,也在孜孜探求其背后的工作原理。今天我们为大家带来的文章,深入浅出地阐释了ChatGPT背后的技术原理,没有NLP或算法经验的小伙伴,也可以轻松理解ChatGPT是如何工作的。以下是译文,Enjoy!......
  • 做题记录(数据结构+整体二分专题)
    情报传递对于每一个操作打上时间戳,对于\(T\)时刻的询问,即为询问路径上比\(T-c\)的值小的数有几个。直接树剖上维护权值树状数组即可。宝石给定一棵树,\(n\)个顶点,每个点有一个宝石,类型为\(W_i\),约定\(W_i\lem\)。你有一个收集器,可以收集至多\(c\)个宝石,并且收集......
  • 智能油田理解一二
    1、油气开采包括钻井工程、油气藏工程、采油气工程、地面工程;接下来才是数字化工程2、建设油气生产物联网,降低劳动强度、缩短故障发现时间,解决【数据有没有问题】3、有了数据带来的问题4、换个角度理解,采集上来的数据带着很多属性,他们渴望被关联、被分析、被挖掘。以增产、降本、增......
  • python中(“{}{}{}”.format(i,j,k))的理解
    “{}{}{}”.format(i,j,k)笼统的来说是字符串的格式化字符串中有一些可以被替换掉的占位符,而格式化的过程就是对这些占位符替换的过程,举例来说:1“Iama{}”.format("student")它表示将字符串"Iama{}"进行格式化,格式化的结果就是该字符串中的占位符{}被format()函数中的参......
  • 【sqlsever】具体案例理解PARTITION BY
    当使用PARTITIONBY时,它通常是与窗口函数一同使用的。下面将提供一个简单的例子,使用一个包含以下列的表:+---------+---------+---------+|column1|column2|column3|+---------+---------+---------+|A|1|10||A|2|20|......