字节跳动第三题正解是什么？

AC 从后往前DP int main() {     int n;     while (cin >> n) {         vector<int> nums(n, 0);         for (int i = 0; i < n; i++) {             cin >> nums[i];         }         vector<int> results(n + 1, 0);         for (int i = n - 1; i >= 0; i--) {             results[i] = (nums[i] + results[i + 1] + 1) / 2;         }         cout << results[0] << endl;     } }

N = int(input()) M = list(map(int,input().split(' '))) L = min(M) R = max(M) def fun(E):     for i in range(N):         if E<M[i]:             E -= M[i] - E         else:             E += E - M[i]         if E<0:             return False     return True while L<R:     mid = (L+R)//2     # 模拟     if not fun(mid):         L = mid + 1     else:         R = mid print(L) Python   100%

每次以能量E跳到下一个，剩余能量都是2*E-H[i+1]，所以倒着推一边就可以了 cin >> n; int *T = new int[n + 1]; for (int i = 1; i <= n; i++) cin >> T[i]; float E = 0.0; for (int i = n - 1; i >= 0; i--) E = (E + T[i+1]) / 2; if (E-(int)E > 0) E = E + 1; cout << (int)E << endl;

在那里还可以看到今天的考试题目吗？？？

有的 #include<bits/stdc++.h> #define MAXN 100006 using namespace std; int N; int h[MAXN]; int check(int energy, int highest){ int e = energy; for(int i=1;i<=N;i++){ e = e * 2 - h[i]; if(e < 0)return 0; if(e >= highest) return 1; } return 1; } int main(){ scanf("%d",&N); int maxi = 0; h[0] = 0; for(int i=1;i<=N;i++){ scanf("%d",&h[i]); if(h[i] > h[maxi]) maxi = i; } int l = 0, r = h[maxi], m; while(l<=r) { m = (l + r)>>1; if(check(m, h[maxi]))r = m - 1; else l = m + 1; } printf("%d\n",l); return 0; }

大家二分有ac的吗

def up_int(num): if int(num) == num: return int(num) else: return int(num)+1 n = int(input()) data = list(map(int, input().split())) dp = [0] * (n+1) # 最后一个位置最小为0 for i in range(n-1, -1, -1): dp[i] = up_int((dp[i+1]+data[i])/2) print(dp[0])

bool judge(LL x, vector<LL> &a) {     LL size = a.size();     for(LL i = 0; i < size; i++)     {         x = 2 * x - a[i];         if(x<0) return false;     }     if(x>=0) return true;     else return false; } 应该是  x = 2*x-aii]，这里会爆long long，因为n很大，所以应该判断下，当能量大于建筑高度最大值时，就直接返回true。

C++ 二分一直在6% 莫非是会爆 long long?

import math if __name__ == "__main__":     n = input()     line = input()     H = line.split(' ')     res = 0     for i in range(int(n)-1,-1,-1):         tmp = math.ceil((int(H[i])+res)/2.0)          res = tmp     print(res) 这个是100%的

同二分，通过4

我是从后往前推的，请问二分思路是怎么样的？

3 1 6 4 这个样例为什么结果是3呀, 那到6的时候不就是负数了吗?

二分 + 跑。 注意加倍的时候不要越界就行

二分没毛病

第三题从后往前推即可AC

没错，二分结果，然后对0的情况特殊讨论一下，完 注意数据范围，两个都是10万

第三题6%