(前缀和)壁画
喜欢就点个赞👍呗,每天都会更新哦!^-^
Problem:
找到数组中的一个连续数组,要求数组的长度不能超过m =(n+1)/ 2
Ideas:
前缀和前m个数组,累加,然后依次往后遍历,每次加上a[i]和减去a[i - m],然后取最大值即可
Code:
滑动窗口
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e6 + 10;
int q = 1; // 第几次的输出
void solve() {
int n;
cin >> n;
string s;
cin >> s;
int a[N]; // 存入数组
for(int i = 0; i < n; i ++ ) {
a[i] = s[i] - '0';
}
int sum = 0;
int m = (n + 1) / 2; // 最多可连续的数组长度
for(int i = 0; i < m; i ++ ) sum += a[i];
int res = sum; // 遍历取max
for(int i = m; i < n; i ++ ) {
sum += a[i];
sum -= a[i - m];
res = max(res, sum);
}
cout << "Case #" << q << ": " << res << endl;
q ++ ;
}
signed main()
{
ios::sync_with_stdio(false), cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while(t -- ) {
solve();
}
}
前缀和
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e6 + 10;
int q = 1; // 第几次的输出
void solve() {
int n;
cin >> n;
string s;
cin >> s;
int a[N]; // 存入数组
for(int i = 0; i < n; i ++ ) {
a[i] = s[i] - '0';
}
int m = (n + 1) / 2; // 最多可连续的数组长度
for(int i = 1; i < n; i++) a[i] = a[i - 1] + a[i];
int res = a[m - 1]; // 遍历取max
for(int i = m; i < n; i ++ ) {
res = max(res, a[i] - a[i - m]);
}
cout << "Case #" << q << ": " << res << endl;
q ++ ;
}
signed main()
{
ios::sync_with_stdio(false), cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while(t -- ) {
solve();
}
}
这个更像是滑动窗口,不是前缀和
确实😋,前缀和应该通过sum[i] - sum[j],我补充一下