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)

class Solution {
public:using ll = long long;  // 定義長整型別名vector<int> piles;     // 存儲香蕉堆的數組int h;                 // 總時間 h 小時int n;                 // 香蕉堆的數量ll ret = INT_MAX;      // 存儲結果，即最小速度 kll maxp;               // 存儲最大的香蕉堆數量// 計算在給定速度下吃完所有香蕉所需的總時間ll f(ll speed) {ll count = 0;  // 總時間for (int i = 0; i < n; i++) {// 計算吃完當前堆香蕉所需的時間count += piles[i] % speed == 0 ? piles[i] / speed : piles[i] / speed + 1;}return count;  // 返回總時間}// 初始化函數，計算香蕉堆的數量和最大的香蕉堆數量void init() {n = piles.size();  // 計算香蕉堆的數量for (int i = 0; i < n; i++) {maxp = fmax(maxp, piles[i]);  // 找到最大的香蕉堆數量}}// 二分查找解決問題void solve() {int l = 1, r = maxp;  // 定義二分查找的左右邊界while (!(l > r)) {    // 當左邊界不大于右邊界時int mid = (l + r) >> 1;  // 計算中間值if (f(mid) <= h) {       // 如果在當前速度下能在 h 小時內吃完所有香蕉ret = fmin(ret, mid);  // 更新最小速度r = mid - 1;           // 縮小右邊界} else {l = mid + 1;           // 否則，增加左邊界}}}// 主函數，計算在 h 小時內吃完所有香蕉的最小速度int minEatingSpeed(vector<int>& _piles, int _h) {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);  // 加速輸入輸出piles = _piles, h = _h;  // 初始化香蕉堆和時間init();                  // 初始化solve();                 // 二分查找解決問題return ret;              // 返回結果}
};

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.

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

class Solution {
public:/*將子數組分成k份,對于每一份子數組,求累加和的最大值.將所有情況的結果最小值求出來固定答案,如果固定答案,意味著所有子數組累加和必須小于limit.這個答案有沒有效果取決于是否可以分成k個子數組.看最小可能分成幾個子數組,如果最小可以分成m個,m<=k*/vector<int> nums;//存儲數組,下標映射元素int k;//分成k份int ret;//結果變量int n;//數組長度int nums_max, sum;//數組元素最大值,和數組累加和int f(int limit) {int count = 0;//可能的最小的分組數int sum = 0;//當前組數的累加和int i = 0;//下一個元素下標//[0,i)//[x,i)while (!(i >= n)) {//遞歸的迭代寫法,出口條件是 i>=n//將i位置元素加入當前組中sum += nums[i];//加入當前組中if (sum > limit) {//如果當前組不能維持累加和小于等于limit,說明此時需要新增一個組count++;//新增一個組sum = nums[i];//這個組累加和是i位置元素}i++;//進入下一個節點}count++;//最后一個組是沒有記錄的,所以需要++操作return count;//返回可能的最小的組數}void init() {n = nums.size();//初始化n變量,數組的元素個數for (int i = 0; i < n; i++) {nums_max = max(nums_max, nums[i]);//初始化nums_maxsum += nums[i];//初始化sum}}void solve() {int l = nums_max, r = sum;//答案的可能范圍是[nums_max,sum]while (l <= r) {//二分所有可能取值int mid = (l + r) >> 1;//中點if (f(mid) <= k) {//如果中點成為答案符合條件ret = mid;//記錄為答案r = mid - 1;//去左邊找可能成為答案你的更小的答案} else {l = mid + 1;//去右邊找}}}int splitArray(vector<int>& _nums, int _k) {nums = _nums, k = _k;init();solve();return ret;}
};

機器人跳躍問題_牛客題霸_牛客網

描述

機器人正在玩一個古老的基于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一直累加有可能會越界.

盡可能進行剪枝操作.

#include <climits>
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'vector<int> arr;//數組,下標映射元素
int n;//數組大小
int nums_max;//數組元素最大值
int ret;//結果變量
bool f(int limit) {int i = 0; //[0,i)int power = limit;//當前能量值,最開始的能力值while (!(i >= n || power < 0)) {//遞歸的迭代寫法if(power>=nums_max)return true;//剪枝操作,當能量大于數組最大值,直接返回trueint diff = abs(arr[i] - power);//計算差值if (arr[i] > power) {//如果i位置高度大于當前能量power -= diff;//能量減少} else {power += diff;//否則能量增加}i++;//進入下一個節點}if (power < 0) {return false;//出來了看一下導致出來的條件是什么//如果能量小于0,返回false} else {return true;//如果能量大于等于0,說明出來的條件是i>=n,返回true}}
void init() {arr.assign(n, 0);//初始化arr數組,分配空間for (int i = 0; i < n; i++) {cin >> arr[i];//初始化每一個元素nums_max = max(nums_max, arr[i]);//初始化nums_max}ret = nums_max;//初始化ret
}
void solve() {int l = 0, r = nums_max;//答案可能的區間是[0,nums_max]while (l <= r) {//二分答案法,二分所有可能值int mid = (l + r) >> 1;//中點值if (f(mid)) {//如果中點符合要求ret = mid;//記錄答案r = mid - 1;//去左邊找} else {l = mid + 1;//去右邊找}}cout << ret;//輸出結果
}signed main() {ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin >> n;init();solve();
}
// 64 位輸出請用 printf("%lld")/*
有下標依次為0~n的建筑.機器人位于某一個建筑,并且有一個能量.
如果機器人要到達下一個建筑,有兩種情況.
首先判斷我的能量和下一個建筑的高度,如果建筑比我的能量高,我就會失去能量.
如果建筑能力比我的能量低或者相等,我就會獲得能量.失去能量和獲得能量,值是高度和能量的差值.
我要到達n號建筑,保證此時能量不為負數.
*/
/*
思路:
首先答案的最大值是數組的最大值nums_max
此時能量都是加,或者不變,一定不會減少,一定可以完成,到達n號建筑.
我們要求可能成為答案的最小值.
二分答案法*/

結尾

最后，感謝您閱讀我的文章，希望這些內容能夠對您有所啟發和幫助。如果您有任何問題或想要分享您的觀點，請隨時在評論區留言。

同時，不要忘記訂閱我的博客以獲取更多有趣的內容。在未來的文章中，我將繼續探討這個話題的不同方面，為您呈現更多深度和見解。

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