笨比暴力法
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 2e5 + 10;
int a[N];
long long add(int l, int r) // 闭区间
{
long long sum = 0;
for (int i = l; i <= r; i++)
sum += a[i];
return sum;
}
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i];
int res = 1, cnt = 1;
long long max1 = a[0];
int tmp = log(n + 1) / log(2); // 共有层数
while (tmp--)
{
if (max1 < add(pow(2, cnt - 1) - 1, pow(2, cnt) - 2))
{
max1 = add(pow(2, cnt - 1) - 1, pow(2, cnt) - 2);
res = cnt;
}
cnt++;
}
if (max1 < add(pow(2, cnt - 1) - 1, n)) // 记得单独补一个对末尾的判断
res = cnt;
cout << res;
return 0;
}
YXC数组双指针
/*
2^(n-1)的写法(1 << (d - 1))或者pow(2,n-1)
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++) // 注意题意,从1开始比较好
cin >> a[i];
long long max1 = -1e9;
int res = 0;
int d = 1; // 层数
for (int i = 1; i <= n; i *= 2) // i表示每层的第一个元素的下标
{
long long sum = 0; // 每层的权值和
// 对同阶层遍历,注意j不能跑到下一层
for (int j = i; j <= n && j < i + pow(2, d - 1); j++)
sum += a[j];
if (max1 < sum)
{
max1 = sum;
res = d;
}
d++;
}
cout << res;
return 0;
}
前缀和
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 1e5 + 10;
long long s[N]; // 前缀和数组
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
int m;
cin >> m;
s[i] = s[i - 1] + m;
}
int res = 0;
int d = 1;
long long max1 = -1e9;
for (int i = 1; i <= n; i = 2 * i)
{
int j = i + pow(2, d - 1) - 1;
if (j > n)
j = n;
// 如果该完全二叉树不是满二叉树,写成break会导致少判断末尾这一段数据
long long sum = s[j] - s[i - 1];
if (max1 < sum)
{
max1 = sum;
res = d;
}
d++;
}
cout << res;
return 0;
}
DFS(通过率11/12,咋回事儿啊)
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 1e5 + 10;
int a[N];
long long sum[N]; // 第i层的权值和
int n;
void dfs(int left, int depth)
{
if (left > n)
return;
int right = left - 1 + pow(2, depth - 1);
if (right > n)
right = n;
for (int i = left; i <= right; i++)
sum[depth] += a[i];
dfs(2 * left, depth + 1);
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
dfs(1, 1); // 每层第一个元素下标,层数
int res = 0;
long long max1 = -1e9;
for (int i = 1; i <= sqrt(n); i++)
if (max1 < sum[i])
{
max1 = sum[i];
res = i;
}
cout << res;
return 0;
}