devbox
AllinToyou
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【九十二】【算法分析与设计】875. 爱吃香蕉的珂珂,410. 分割数组的最大值,机器人跳跃问题,二分答案法

作者：AllinToyou | 2024-05-23 22:47:52

赞

踩

【九十二】【算法分析与设计】875. 爱吃香蕉的珂珂,410. 分割数组的最大值,机器人跳跃问题,二分答案法

875. 爱吃香蕉的珂珂 - 力扣（LeetCode）

珂珂喜欢吃香蕉。这里有 n 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 h 小时后回来。

珂珂可以决定她吃香蕉的速度 k （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 k 根。如果这堆香蕉少于 k 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。

珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。

返回她可以在 h 小时内吃掉所有香蕉的最小速度 k（k 为整数）。

示例 1：

输入：piles = [3,6,7,11], h = 8 输出：4

示例 2：

输入：piles = [30,11,23,4,20], h = 5 输出：30

示例 3：

输入：piles = [30,11,23,4,20], h = 6 输出：23

提示：

  • 1 <= piles.length <= 10(4)

  • piles.length <= h <= 10(9)

  • 1 <= piles[i] <= 10(9)

 

  1. class Solution {
  2. public:
  3.     using ll = long long;  // 定义长整型别名
  4.     vector<int> piles;     // 存储香蕉堆的数组
  5.     int h;                 // 总时间 h 小时
  6.     int n;                 // 香蕉堆的数量
  7.     ll ret = INT_MAX;      // 存储结果，即最小速度 k
  8.     ll maxp;               // 存储最大的香蕉堆数量
  9.     
  10.     // 计算在给定速度下吃完所有香蕉所需的总时间
  11.     ll f(ll speed) {
  12.         ll count = 0;  // 总时间
  13.         for (int i = 0; i < n; i++) {
  14.             // 计算吃完当前堆香蕉所需的时间
  15.             count += piles[i] % speed == 0 ? piles[i] / speed : piles[i] / speed + 1;
  16.         }
  17.         return count;  // 返回总时间
  18.     }
  19.     
  20.     // 初始化函数，计算香蕉堆的数量和最大的香蕉堆数量
  21.     void init() {
  22.         n = piles.size();  // 计算香蕉堆的数量
  23.         for (int i = 0; i < n; i++) {
  24.             maxp = fmax(maxp, piles[i]);  // 找到最大的香蕉堆数量
  25.         }
  26.     }
  27.     
  28.     // 二分查找解决问题
  29.     void solve() {
  30.         int l = 1, r = maxp;  // 定义二分查找的左右边界
  31.         while (!(l > r)) {    // 当左边界不大于右边界时
  32.             int mid = (l + r) >> 1;  // 计算中间值
  33.             if (f(mid) <= h) {       // 如果在当前速度下能在 h 小时内吃完所有香蕉
  34.                 ret = fmin(ret, mid);  // 更新最小速度
  35.                 r = mid - 1;           // 缩小右边界
  36.             } else {
  37.                 l = mid + 1;           // 否则，增加左边界
  38.             }
  39.         }
  40.     }
  41.     
  42.     // 主函数，计算在 h 小时内吃完所有香蕉的最小速度
  43.     int minEatingSpeed(vector<int>& _piles, int _h) {
  44.         ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);  // 加速输入输出
  45.         piles = _piles, h = _h;  // 初始化香蕉堆和时间
  46.         init();                  // 初始化
  47.         solve();                 // 二分查找解决问题
  48.         return ret;              // 返回结果
  49.     }
  50. };
 

410. 分割数组的最大值 - 力扣（LeetCode）
 

 
 
给定一个非负整数数组 nums 和一个整数 k ，你需要将这个数组分成 k 个非空的连续子数组。
 
 
设计一个算法使得这 k 个子数组各自和的最大值最小。
 
 
示例 1：
 
 
输入：nums = [7,2,5,10,8], k = 2 输出：18 解释： 一共有四种方法将 nums 分割为 2 个子数组。 其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。 因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。
 
 
示例 2：
 
 
输入：nums = [1,2,3,4,5], k = 2 输出：9
 
 
示例 3：
 
 
输入：nums = [1,4,4], k = 3 输出：4
 
 
提示：
 
 
  •  
    1 <= nums.length <= 1000
     
  •  
    0 <= nums[i] <= 10(6)
     
  •  
    1 <= k <= min(50, nums.length)
     
 

 

1.
 

创建变量的时候注意赋予初值,ACM模式可能会发生错误,养成好习惯,赋初值.
 

2.
 

二分答案法,固定答案寻找符合要求的答案值.
 

 

  1. class Solution {
  2. public:
  3.     /*
  4.     将子数组分成k份,对于每一份子数组,求累加和的最大值.将所有情况的结果最小值求出来
  5.     固定答案,如果固定答案,意味着所有子数组累加和必须小于limit.
  6.     这个答案有没有效果取决于是否可以分成k个子数组.
  7.     看最小可能分成几个子数组,如果最小可以分成m个,m<=k
  8.     */
  9.     vector<int> nums;//存储数组,下标映射元素
  10.     int k;//分成k份
  11.     int ret;//结果变量
  12.  
  13.     int n;//数组长度
  14.     int nums_max, sum;//数组元素最大值,和数组累加和
  15.  
  16.     int f(int limit) {
  17.         int count = 0;//可能的最小的分组数
  18.         int sum = 0;//当前组数的累加和
  19.         int i = 0;//下一个元素下标
  20.         //[0,i)
  21.         //[x,i)
  22.         while (!(i >= n)) {//递归的迭代写法,出口条件是 i>=n
  23.             //将i位置元素加入当前组中
  24.             sum += nums[i];//加入当前组中
  25.             if (sum > limit) {//如果当前组不能维持累加和小于等于limit,说明此时需要新增一个组
  26.                 count++;//新增一个组
  27.                 sum = nums[i];//这个组累加和是i位置元素
  28.             }
  29.             i++;//进入下一个节点
  30.         }
  31.         count++;//最后一个组是没有记录的,所以需要++操作
  32.         return count;//返回可能的最小的组数
  33.     }
  34.     void init() {
  35.         n = nums.size();//初始化n变量,数组的元素个数
  36.         for (int i = 0; i < n; i++) {
  37.             nums_max = max(nums_max, nums[i]);//初始化nums_max
  38.             sum += nums[i];//初始化sum
  39.         }
  40.     }
  41.     void solve() {
  42.         int l = nums_max, r = sum;//答案的可能范围是[nums_max,sum]
  43.         while (l <= r) {//二分所有可能取值
  44.             int mid = (l + r) >> 1;//中点
  45.             if (f(mid) <= k) {//如果中点成为答案符合条件
  46.                 ret = mid;//记录为答案
  47.                 r = mid - 1;//去左边找可能成为答案你的更小的答案
  48.             } else {
  49.                 l = mid + 1;//去右边找
  50.             }
  51.         }
  52.     }
  53.  
  54.     int splitArray(vector<int>& _nums, int _k) {
  55.         nums = _nums, k = _k;
  56.         init();
  57.         solve();
  58.         return ret;
  59.     }
  60. };
 

机器人跳跃问题_牛客题霸_牛客网
 

 
 
描述
 
 
机器人正在玩一个古老的基于DOS的游戏。游戏中有N+1座建筑——从0到N编号，从左到右排列。编号为0的建筑高度为0个单位，编号为i的建筑的高度为H(i)个单位。
 
 
 
 
起初， 机器人在编号为0的建筑处。每一步，它跳到下一个（右边）建筑。假设机器人在第k个建筑，且它现在的能量值是E, 下一步它将跳到第个k+1建筑。它将会得到或者失去正比于与H(k+1)与E之差的能量。如果 H(k+1) > E 那么机器人就失去 H(k+1) - E 的能量值，否则它将得到 E - H(k+1) 的能量值。
 
 
 
 
游戏目标是到达第个N建筑，在这个过程中，能量值不能为负数个单位。现在的问题是机器人以多少能量值开始游戏，才可以保证成功完成游戏？
 
 
输入描述：
 
 
第一行输入，表示一共有 N 组数据. 第二个是 N 个空格分隔的整数，H1, H2, H3, ..., Hn 代表建筑物的高度
 
 
输出描述：
 
 
输出一个单独的数表示完成游戏所需的最少单位的初始能量
 
 
示例1
 
 
输入：
 
 
5 3 4 3 2 4
 
 
复制
 
 
输出：
 
 
4
 
 
复制
 
 
示例2
 
 
输入：
 
 
3 4 4 4
 
 
复制
 
 
输出：
 
 
4
 
 
复制
 
 
示例3
 
 
输入：
 
 
3 1 6 4
 
 
复制
 
 
输出：
 
 
3
 
 
复制
 
 
备注：
 
 
数据约束：
 
 
1 <= N <= 10^5
 
 
1 <= H(i) <= 10^5
 

 

1.
 

养成好习惯,变量赋初值.
 

2.
 

代码过不去可能不是代码逻辑错误,有可能是变量在运行过程中是否越界.
 

power一直累加有可能会越界.
 

尽可能进行剪枝操作.
 

  1. #include <climits>
  2. #include <iostream>
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5. #define int long long
  6. #define endl '\n'
  7.  
  8. vector<int> arr;//数组,下标映射元素
  9. int n;//数组大小
  10. int nums_max;//数组元素最大值
  11. int ret;//结果变量
  12. bool f(int limit) {
  13.     int i = 0; //[0,i)
  14.     int power = limit;//当前能量值,最开始的能力值
  15.     while (!(i >= n || power < 0)) {//递归的迭代写法
  16.         if(power>=nums_max)return true;//剪枝操作,当能量大于数组最大值,直接返回true
  17.         int diff = abs(arr[i] - power);//计算差值
  18.  
  19.         if (arr[i] > power) {//如果i位置高度大于当前能量
  20.             power -= diff;//能量减少
  21.         } else {
  22.             power += diff;//否则能量增加
  23.         }
  24.         i++;//进入下一个节点
  25.     }
  26.  
  27.     if (power < 0) {
  28.         return false;//出来了看一下导致出来的条件是什么
  29.         //如果能量小于0,返回false
  30.     } else {
  31.         return true;//如果能量大于等于0,说明出来的条件是i>=n,返回true
  32.     }
  33.  
  34. }
  35. void init() {
  36.     arr.assign(n, 0);//初始化arr数组,分配空间
  37.     for (int i = 0; i < n; i++) {
  38.         cin >> arr[i];//初始化每一个元素
  39.         nums_max = max(nums_max, arr[i]);//初始化nums_max
  40.     }
  41.     ret = nums_max;//初始化ret
  42. }
  43. void solve() {
  44.     int l = 0, r = nums_max;//答案可能的区间是[0,nums_max]
  45.     while (l <= r) {//二分答案法,二分所有可能值
  46.         int mid = (l + r) >> 1;//中点值
  47.  
  48.         if (f(mid)) {//如果中点符合要求
  49.             ret = mid;//记录答案
  50.             r = mid - 1;//去左边找
  51.         } else {
  52.             l = mid + 1;//去右边找
  53.         }
  54.     }
  55.  
  56.     cout << ret;//输出结果
  57. }
  58.  
  59. signed main() {
  60.     ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  61.     cin >> n;
  62.     init();
  63.     solve();
  64. }
  65. // 64 位输出请用 printf("%lld")
  66.  
  67. /*
  68. 有下标依次为0~n的建筑.机器人位于某一个建筑,并且有一个能量.
  69. 如果机器人要到达下一个建筑,有两种情况.
  70. 首先判断我的能量和下一个建筑的高度,如果建筑比我的能量高,我就会失去能量.
  71. 如果建筑能力比我的能量低或者相等,我就会获得能量.
  73. 失去能量和获得能量,值是高度和能量的差值.
  74. 我要到达n号建筑,保证此时能量不为负数.
  75. */
  76. /*
  77. 思路:
  78. 首先答案的最大值是数组的最大值nums_max
  79. 此时能量都是加,或者不变,一定不会减少,一定可以完成,到达n号建筑.
  80. 我们要求可能成为答案的最小值.
  81. 二分答案法
  83. */
 

结尾
 

最后，感谢您阅读我的文章，希望这些内容能够对您有所启发和帮助。如果您有任何问题或想要分享您的观点，请随时在评论区留言。
 

 

同时，不要忘记订阅我的博客以获取更多有趣的内容。在未来的文章中，我将继续探讨这个话题的不同方面，为您呈现更多深度和见解。
 

 

谢谢您的支持，期待与您在下一篇文章中再次相遇！

                

        
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/AllinToyou/article/detail/614705
推荐阅读
相关标签
Copyright ©  2003-2013 www.wpsshop.cn  版权所有，并保留所有权利。

  
闽ICP备14008679号