while循环做法
可以省去一些计算 但是细节要注意 比如最后一段不能到最后需要加上条件限制
#include "bits/stdc++.h"
using namespace std;
const int N = 1e5 + 10;
int n, a[N], res;
long long maxv = INT_MIN, s;
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i];
for (int i = 0, j = 0; i < n; i++)
{
if (j >= n)
break;
while (j < (1 << i + 1) - 1 && j < n)
s += a[j++];
if (s > maxv)
{
maxv = s;
res = i;
}
s = 0;
}
return cout << res + 1, 0;
}
前缀和做法
2^0 + 2^1 + ...... + 2^(d-1) <= n ===> 2^d - 1 <= n ===> d <= log(n + 1) / log2 + 1
log()函数以e为底。 也可以直接判断pow(2, d) - 1是否小于等于n
求一个区间的右端点时需要判断是否越界 越界的话令其为n
#include "bits/stdc++.h"
using namespace std;
const int N = 1e5 + 10;
long long n, q[N];
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> q[i], q[i] += q[i - 1];
long long s = 0;
long long maxv = INT_MIN, res = 0;
for (int d = 1; d <= log(n + 1) / log(2) + 1; d++)
{
int r = (1 << d) - 1 <= n ? (1 << d) - 1 : n, l = (1 << d - 1);
s = q[r] - q[l - 1];
if (s > maxv)
maxv = s, res = d;
}
cout << res;
return 0;
}
更新
不可以直接使用pow(2, d) - 1 <= n,这样会忽略掉最后一段不完整的那段。即n往前的一段
大佬您好,我看了您的题解想问一下,d <= log(n + 1) / log2 + 1这里为什么要加上1呢,是不是因为要上取整?如果是因为要上取整是为什么要这样做?不太明白
要向上取整是因为最后一层可能不满,此时计算 $\log_2 n+1$ 会比实际层数少一层,所以要加 1 。
就是下面的解释 也可以直接上面的第一种做法 不用考虑那么多 下标超过n就直接结束