草庐IT

C++算法之旅、02 从木棒切割问题领悟二分法精髓

小能的博客 CanAngle's Blog 2023-03-28 原文

172、木棒切割问题

https://sunnywhy.com/problem/172


题目描述

给出n根木棒的长度，现在希望通过切割它们来得到至少k段长度相等的木棒（长度必须是整数），问这些长度相等的木棒的最大长度。


输入描述

第一行为两个正整数n、k（1≤n≤103、1≤k≤108），分别表示木棒的根数、需要得到的长度相等的木棒根数；

第二行为n个整数（1≤每个整数≤105），表示木棒的长度。


输出描述

一个整数，表示木棒的最大长度。如果无法达成，此时最大长度为0。


思考

如果通过暴力解法，那么复杂度为\(O(n^2)\)。每轮选择一个长度遍历每根绳子。

已知木棒分割的长度为正整数，且位于\([1,max(每根绳子的长度)]\)区间。当前为有序序列。求解至少k段长度相等木棒时，木棒的最大长度。

有序序列+求第一个满足某条件的元素的位置 => 二分法


已知木棒分割的长度序列从小到大，那么每个木棒长度对应的木棒段数序列从大到小。

那么求木棒的最大长度，实际上在求最后一个 >= k 的木棒段数此时的木棒长度 。


但二分法是求第一个满足某条件的元素位置，为什么呢？不妨先试着编写求最后一个满足某条件元素位置的二分法。

假定序列从小到大排列，可以很容易写出下面三种情况。但在测试过程中，往往会出现死循环或没有输出的现象。

第1、3种情况无论如何也会让 \(left < right\) 不成立从而退出\(while\)循环。

那么很可能在第2种情况的时候陷入了死循环，求解一下死循环成立的条件。

\(\frac{left+right}{2} = left \\ \frac{right}{2} = \frac{left}{2} \\ \text 这是C语言的整除\)

二分法求解给定的\(while\)条件是\(left < right\)。显而易见，当left、right为相邻的奇偶时，且当 \(A[mid] == x\) 时，会无限死循环，每轮都会进入第2种情况。

所以牢记二分法用于寻找有序序列第一个满足某条件的元素的位置。

题解很简单，我们只需要求第一个分段数小于k的木棒长度然后减1即可。


解法

// https://sunnywhy.com/problem/172

// 考察二分查找

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>

int countSticks(int ans[], int len, int sep) {
    int total = 0;
    for (int i = 0; i < len; i++) {
        total += ans[i] / sep;
    }
    return total;
}

int main() {
    int n, k, ans[1010], max = 0;
    // 加载数据
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++) {
        scanf("%d", &ans[i]);
        if (ans[i] > max) {
            max = ans[i];
        }
    }
    // 逻辑处理
    int mid, left = 1, right = max;
    while (left < right) {
        mid = (left + right) / 2;
        if (countSticks(ans, n, mid) < k) {
            right = mid;
        } else {
            left = mid + 1;
        }
    };
    printf("%d\n", --left);

    return 0;
}

二分法固定模板

C++木棒strong二分算法与数据结构

有关C++算法之旅、02 从木棒切割问题领悟二分法精髓的更多相关文章

  1. ruby - 在 64 位 Snow Leopard 上使用 rvm、postgres 9.0、ruby 1.9.2-p136 安装 pg gem 时出现问题 - 2

    我想为Heroku构建一个Rails3应用程序。他们使用Postgres作为他们的数据库，所以我通过MacPorts安装了postgres9.0。现在我需要一个postgresgem并且共识是出于性能原因你想要pggem。但是我对我得到的错误感到非常困惑当我尝试在rvm下通过geminstall安装pg时。我已经非常明确地指定了所有postgres目录的位置可以找到但仍然无法完成安装:$envARCHFLAGS='-archx86_64'geminstallpg--\--with-pg-config=/opt/local/var/db/postgresql90/defaultdb/po

  2. ruby - 通过 rvm 升级 ruby​​gems 的问题 - 2

    尝试通过RVM将RubyGems升级到版本1.8.10并出现此错误:$rvmrubygemslatestRemovingoldRubygemsfiles...Installingrubygems-1.8.10forruby-1.9.2-p180...ERROR:Errorrunning'GEM_PATH="/Users/foo/.rvm/gems/ruby-1.9.2-p180:/Users/foo/.rvm/gems/ruby-1.9.2-p180@global:/Users/foo/.rvm/gems/ruby-1.9.2-p180:/Users/foo/.rvm/gems/rub

  3. ruby - 通过 RVM (OSX Mountain Lion) 安装 Ruby 2.0.0-p247 时遇到问题 - 2

    我的最终目标是安装当前版本的RubyonRails。我在OSXMountainLion上运行。到目前为止，这是我的过程:已安装的RVM$\curl-Lhttps://get.rvm.io|bash-sstable检查已知(我假设已批准)安装$rvmlistknown我看到当前的稳定版本可用[ruby-]2.0.0[-p247]输入命令安装$rvminstall2.0.0-p247注意:我也试过这些安装命令$rvminstallruby-2.0.0-p247$rvminstallruby=2.0.0-p247我很快就无处可去了。结果:$rvminstall2.0.0-p247Search

  4. ruby - Fast-stemmer 安装问题 - 2

    由于fast-stemmer的问题，我很难安装我想要的任何ruby​​gem。我把我得到的错误放在下面。Buildingnativeextensions.Thiscouldtakeawhile...ERROR:Errorinstallingfast-stemmer:ERROR:Failedtobuildgemnativeextension./System/Library/Frameworks/Ruby.framework/Versions/2.0/usr/bin/rubyextconf.rbcreatingMakefilemake"DESTDIR="cleanmake"DESTDIR=

  5. ruby - 安装 Ruby 时遇到问题(无法下载资源 "readline--patch") - 2

    当我尝试安装Ruby时遇到此错误。我试过查看this和this但无济于事➜~brewinstallrubyWarning:YouareusingOSX10.12.Wedonotprovidesupportforthispre-releaseversion.Youmayencounterbuildfailuresorotherbreakages.Pleasecreatepull-requestsinsteadoffilingissues.==>Installingdependenciesforruby:readline,libyaml,makedepend==>Installingrub

  6. java - 从 JRuby 调用 Java 类的问题 - 2

    我正在尝试使用boilerpipe来自JRuby。我看过guide从JRuby调用Java，并成功地将它与另一个Java包一起使用，但无法弄清楚为什么同样的东西不能用于boilerpipe。我正在尝试基本上从JRuby中执行与此Java等效的操作:URLurl=newURL("http://www.example.com/some-location/index.html");Stringtext=ArticleExtractor.INSTANCE.getText(url);在JRuby中试过这个:require'java'url=java.net.URL.new("http://www

  7. ruby-on-rails - 简单的 Ruby on Rails 问题——如何将评论附加到用户和文章？ - 2

    我意识到这可能是一个非常基本的问题，但我现在已经花了几天时间回过头来解决这个问题，但出于某种原因，Google就是没有帮助我。(我认为部分问题在于我是一个初学者，我不知道该问什么......)我也看过O'Reilly的RubyCookbook和RailsAPI，但我仍然停留在这个问题上.我找到了一些关于多态关系的信息，但它似乎不是我需要的(尽管如果我错了请告诉我)。我正在尝试调整MichaelHartl'stutorial创建一个包含用户、文章和评论的博客应用程序(不使用脚手架)。我希望评论既属于用户又属于文章。我的主要问题是:我不知道如何将当前文章的ID放入评论Controller。

  8. 【高数】用拉格朗日中值定理解决极限问题 - 2

    首先回顾一下拉格朗日定理的内容：函数f(x)是在闭区间[a,b]上连续、开区间(a,b)上可导的函数，那么至少存在一个，使得:通过这个表达式我们可以知道，f(x)是函数的主体，a和b可以看作是主体函数f(x)中所取的两个值。那么可以有，  也就意味着我们可以用来替换 这种替换可以用在求某些多项式差的极限中。方法： 外层函数f(x)是一致的，并且h(x)和g(x)是等价无穷小。此时，利用拉格朗日定理，将原式替换为 ，再进行求解，往往会省去复合函数求极限的很多麻烦。使用要注意：1.要先找到主体函数f(x)，即外层函数必须相同。2.f(x)找到后，复合部分是等价无穷小。3.要满足作差的形式。如果是加

  9. 区块链之加解密算法&数字证书 - 2

    目录一.加解密算法数字签名对称加密DES(DataEncryptionStandard)3DES(TripleDES)AES(AdvancedEncryptionStandard)RSA加密法DSA(DigitalSignatureAlgorithm)ECC(EllipticCurvesCryptography)非对称加密签名与加密过程非对称加密的应用对称加密与非对称加密的结合二.数字证书图解一.加解密算法加密简单而言就是通过一种算法将明文信息转换成密文信息，信息的的接收方能够通过密钥对密文信息进行解密获得明文信息的过程。根据加解密的密钥是否相同，算法可以分为对称加密、非对称加密、对称加密和非

  10. postman——集合——执行集合——测试脚本——pm对象简单示例02 - 2

    //1.验证返回状态码是否是200pm.test("Statuscodeis200",function(){pm.response.to.have.status(200);});//2.验证返回body内是否含有某个值pm.test("Bodymatchesstring",function(){pm.expect(pm.response.text()).to.include("string_you_want_to_search");});//3.验证某个返回值是否是100pm.test("Yourtestname",function(){varjsonData=pm.response.json

随机推荐