社区讨论
求助P1114
灌水区参与者 2已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @m2kbvii6
- 此快照首次捕获于
- 2024/10/22 18:54 去年
- 此快照最后确认于
- 2025/11/04 16:31 4 个月前
为啥wa了三个点,思路就是记录第一次出现与最后出现位置,用前缀和
CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
int a[100005];
int sum[100005],maxn,ans;
map<int,int>stat;
map<int,int>last;
int read(){
int x=0,f=1;
char ch = getchar();
while (ch < 48 || ch > 57){
if (ch == 45){
f = -1;
}
ch = getchar();
}
while (ch >= 48 && ch <= 57){
x = (x << 1) + (x << 3) + (ch - 48);
ch = getchar();
}
return x * f;
}
signed main(){
n = read();
for (int i=1; i<=n; i++){
a[i] = read();
if (a[i] == 0) a[i] = -1;
sum[i] = sum[i-1]+a[i];
stat[sum[i]] = 0;
last[sum[i]] = 0;
}
for (int i=1; i<=n; i++){
last[sum[i]] = i;
if (stat[sum[i]] > 0){
continue;
}
else {
stat[sum[i]] = i;
}
}
for (int i=1; i<=n; i++){
if (stat[sum[i]] == last[sum[i]]){
continue;
}
ans = last[sum[i]] - stat[sum[i]];
maxn = max(ans,maxn);
}
cout << maxn;
return 0;
}
回复
共 1 条回复,欢迎继续交流。
正在加载回复...