C++算法之旅、02 从木棒切割问题领悟二分法精髓
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即可。
解法
// //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++算法之旅、02 从木棒切割问题领悟二分法精髓的更多相关文章
- HDU 5984(求木棒切割期望 数学)
题意是给定一长为 L 的木棒,每次任意切去一部分直到剩余部分的长度不超过 D,求切割次数的期望. 若木棒初始长度不超过 D,则期望是 0.000000: 设切割长度为 X 的木棒切割次数的期望是 F( ...
- LeetCode初级算法--设计问题02：最小栈
LeetCode初级算法--设计问题02:最小栈 搜索微信公众号:'AI-ming3526'或者'计算机视觉这件小事' 获取更多算法.机器学习干货 csdn://blog.csdn.net ...
- Paxos算法之旅（四）zookeeper代码解析--转载
ZooKeeper是近期比较热门的一个类Paxos实现.也是一个逐渐得到广泛应用的开源的分布式锁服务实现.被认为是Chubby的开源版,虽然具体实现有很多差异.ZooKeeper概要的介绍可以看官方文 ...
- js算法初窥02（排序算法02-归并、快速以及堆排序）
上一篇,我们讲述了一些简单的排序算法,其实说到底,在前端的职业生涯中,不涉及node.不涉及后台的情况下,我目前还真的没想到有哪些地方可以用到这些数据结构和算法,但是我在前面的文章也说过了.或许你用不 ...
- 算法之旅，直奔<algorithm>之十七 find_first_of
find_first_of(vs2010) 引言 这是我学习总结 <algorithm>的第十七篇,find_first_of是匹配的一个函数.<algorithm>是c++的 ...
- 算法之旅，直奔<algorithm>之十三 fill
fill(vs2010) 引言 这是我学习总结<algorithm>的第十三篇,fill是一个很好的初始化工具.大学挺好,好好珍惜... 作用 fill 的作用是 给容器里一个指定的范围 ...
- 算法之旅，直奔<algorithm>之十四 fill_n
fill_n(vs2010) 引言 这是我学习总结<algorithm>的第十四篇,作为fill的亲兄弟,fill_n也会助你一把的. 作用 fill_n 的作用是给一段指定长度的数据向量 ...
- 算法之旅，直奔<algorithm>之十五 find
find(vs2010) 引言 这是我学习总结 <algorithm>的第十五篇.关于<algorithm>,每篇都很小,但是都很好用,可以秀出你的个性. 作用 find的作用 ...
- 算法之旅，直奔<algorithm>之十 count_if
count_if(vs2010) 引言 这是我学习总结<algorithm>的第十篇,这个重要的地方是设置条件.用的还是蛮多的.(今天下午挺恶心的,一下午就做一个面试题,调代码调傻了... ...
随机推荐
- Spring源码 13 IOC refresh方法8
本文章基于 Spring 5.3.15 Spring IOC 的核心是 AbstractApplicationContext 的 refresh 方法. 其中一共有 13 个主要方法,这里分析第 8 ...
- Taurus.MVC 微服务双色球129期开奖结果
入门开发教程：项目部署：6、微服务应用程序Docker部署实现多开。
系列目录: 本系列分为项目集成.项目部署.架构演进三个方向,后续会根据情况调整文章目录. 开源地址://github.com/cyq1162/Taurus.MVC 本系列第一篇:Tauru ...
- React报错之Rendered more hooks than during the previous render
正文从这开始~ 总览 当我们有条件地调用一个钩子或在所有钩子运行之前提前返回时,会产生"Rendered more hooks than during the previous render ...
- Springboot mybatis总结
mybatis 总结 属性配置 1. mybatis.configuration.mapUnderscoreToCamelCase=true mapUnderscoreToCamelCase用于映射表 ...
- mysql explain总结
Explain 包含字段 id select_type table type possible_keys key key_len ref rows extra 字段解释 1. id id 相同则执行顺 ...
- Liquibase-数据库版本管理控制
1. 简介 Liquibase是一个用于跟踪.管理和应用数据库变化的开源的数据库重构工具.它将所有数据库的变化(包括结构和数据)都保存在XML文件中,便于版本控制. Liquibase使参与应用程序发 ...
- 基于 vite 创建 vue3 全家桶项目（vite + vue3 + tsx + pinia）
vite 最近非常火,它是 vue 作者尤大神发布前端构建工具,底层基于 Rollup,无论是启动速度还是热加载速度都非常快.vite 随 vue3 正式版一起发布,刚开始的时候与 vue 绑定在一起 ...
- [LeetCode]-217.存在重复元素-简单
217. 存在重复元素 给定一个整数数组,判断是否存在重复元素. 如果存在一值在数组中出现至少两次,函数返回 true .如果数组中每个元素都不相同,则返回 false . 示例 1: 输入: [1, ...
- 使用kuboard部署某一个应用的pod分布于不同的主机上
情况介绍 1.k8s集群有8个节点,3个节点是master,分别是master1,master2,master3. 5个worker节点,分别是worker1,worke2,worke3,worker ...
- 使用工具SecureCRT通过ssh远程连接Windows server 2019
Windows Server 2019 开通SSH Server服务 在需要安裝的ws2019开启powershell,执行安装 openssh server 指令 Add-WindowsCapabi ...