二分答案
#include<bits/stdc++.h>using namespace std;bool check(vector<long long>& a, long long mid){ long long temp; for(int i=0; i<a.size()-1; i++){ temp = min(a[i]*2, mid/2); if(a[i]>temp) return false; mid -= temp; } return mid >= a.back();}int main(){ // freopen("in.dat", "r", stdin); vector<long long> a; long long x; while(cin>>x){ a.push_back(x); } long long l = 1; long long r = 0x3f3f3f3f3f3f3f3fL; while(l<r){ long long mid = (r+l) / 2; if(check(a, mid)){; r = mid; }else{ l = mid + 1; } } cout<<r<<endl; return 0;}
相似题目：
leetcode 875 爱吃香蕉的健康的小松鼠
思路：二分法找最小吃香蕉速度，当恰好吃完（Math.ceil(p / K) = ((p-1) // K) + 1），返回速度K。
为什么找左侧边界？
根据题意，健康的小松鼠最快一个小时吃完一堆，假设这个速度为Kmax。
那么就是需要在[0,…,Kmax]的区间里找到健康的小松鼠可以在指定时间内，吃得最慢的速度。
在这个区间内能在H时间内吃完的值有许多，我们需要找到最小的值，也就是需要找到满足条件区间的最左侧的值。
左侧边界means符合条件的有一个区间，我们想找到这个区间的最左侧的值。
条件means如果要在数组中找一个target，那么条件是target <= nums[mid]。在本道题中，就是Math.ceil(p / K) <= H.
官方写法：
class Solution(object): def minEatingSpeed(self, piles, H): # Can Koko eat all bananas in H hours with eating speed K? def possible(K): return sum((p-1) / K + 1 for p in piles) <= H lo, hi = 1, max(piles) while lo < hi: mi = (lo + hi) / 2 if not possible(mi): lo = mi + 1 else: hi = mi return lo
我的写法：
import mathclass Solution: def minEatingSpeed(self, piles: List[int], h: int) -> int: def finish(k): return sum(math.ceil(piles[i] / k) for i in range(len(piles))) <= h l, r = 1, max(piles) while l <= r: mid = l + (r - l) // 2 if finish(mid): r = mid - 1 else: l = mid + 1 return l
单调队列
#include<bits/stdc++.h>using namespace std;int main(){ int n,m; cin>>n>>m; vector<int> a(n+1, 0); for(int i=0; i<n; i++){ cin>>a[i+1]; a[i+1] += a[i]; } deque<int> que; int ans = 0; for(int i=0; i<=n; i++){ while(!que.empty() && que.front()+m<i ){ que.pop_front(); } if(!que.empty()) ans = max(ans, a[i] - a[que.front()]); while(!que.empty() && a[que.back()] >= a[i]){ que.pop_back(); } que.push_back(i); } cout<<ans<<endl; return 0;}
相似题目：
leetcode 1425， 1696
数学方法，倒着求
要么是直接减到， 否则就分情况，偶数直接除2， 奇数求一个+1， -1的最小值
#include<bits/stdc++.h>using namespace std;unsigned long long n, a, b;long long dfs(unsigned long long n){ if(n==0) return 0; if(n==1) return b; unsigned long long res = min( min(dfs(n/2) + a + b*(n%2), b*n), dfs(n/2) + b*(n-n/2)); return min(res, dfs((n+1)/2) + a + b*(n%2));}int main(){// freopen("in.dat", "r", stdin); cin>>n>>b>>a; cout<<dfs(n)<<endl; return 0;}
// dp[i][j][k] 表示前i个字母，修改j次，第一个字母有k个的时候的最大结果
// 特判t的两个字母相等的情况
#include<bits/stdc++.h>using namespace std;// dp[i][j][k] 表示前i个字母，修改不超过j次，第一个字母有k个的情况long long dp[210][210][210];const long long inf = LLONG_MIN;int main(){// freopen("in.dat", "r", stdin); int n,k; cin>>n>>k; string s,t; cin>>s; cin>>t; if(t[0]==t[1]){ int cnt=0; ; for(int i=0; i<n; i++){ if(k&&s[i]!=t[0]){ k--; s[i]=t[0]; } cnt += s[i]==t[0]; } cout<<cnt*(cnt-1)/2<<endl; return 0; } for(int i=0; i<210; i++){ for(int j=0; j<210; j++){ for(int m=0; m<210; m++) dp[i][j][m] = inf; } } dp[0][0][0] = 0; for(int i=0; i<s.size(); i++){ for(int j=0; j<=k; j++){ for(int m=0; m<=s.size(); m++){ if(dp[i][j][m]==inf) continue; if(s[i]==t[1]) { //当前位是1 dp[i+1][j][m] = max(dp[i][j][m]+m, dp[i+1][j][m]); dp[i+1][j+1][m+1] = max(dp[i+1][j+1][m+1], dp[i][j][m]); } if(s[i]==t[0]){ //当前位是0； dp[i+1][j][m+1] = max(dp[i+1][j][m+1], dp[i][j][m]); dp[i+1][j+1][m] = max(dp[i][j][m]+m, dp[i+1][j+1][m]); } //变成0 dp[i+1][j+1][m+1] = max(dp[i+1][j+1][m+1], dp[i][j][m]); //变成1 dp[i+1][j+1][m] = max(dp[i][j][m]+m, dp[i+1][j+1][m]); dp[i+1][j][m] = max(dp[i+1][j][m], dp[i][j][m]); } } } long long ans = inf; for(int i=0; i<=k; i++){ for(int j=0; j<=n; j++){ ans = max(ans, dp[n][i][j]); } } cout<<ans<<endl; return 0;}
reference：
https://www.nowcoder.com/discuss/619619?type=2&channel=-1&source_id=discuss_terminal_discuss_hot_nctrack&page=2
https://www.nowcoder.com/discuss/619638?type=post&order=time&pos=&page=1&channel=-1&source_id=search_post_nctrack
https://pastebin.ubuntu.com/p/TbHdFYM4HR/plain/
https://pastebin.ubuntu.com/p/32pb2kZjDP/
http://pastebin.ubuntu.com/p/7cgSqVfnc3/plain/
https://pastebin.ubuntu.com/p/hH4PDQbQTD/
https://leetcode-cn.com/problems/koko-eating-bananas/solution/ai-chi-xiang-jiao-de-ke-ke-by-leetcode/
https://leetcode-cn.com/problems/koko-eating-bananas/solution/sou-suo-zuo-ce-bian-jie-de-er-fen-suan-f-cgmh/