【题解】平衡区间
题意
给你一个数组,求最大的区间
使得
题解
首先看数据范围,,
只有两种取值范围。那么转换一下题意就变成了最长的区间,这个区间中
和
的数量是一样多的。那么我们可以怎么处理呢,我们可以将
用
来替换,然后对数组
求一个前缀和。然后可以分两种情况考虑。
- 若
说明
的区间内
和
的个数是一样的。
- 若
说明
这个区间之内
和
的数量是一样多的,因为前缀和是一样的,说明
和
的个数抵消了。
我们去记录每个和所对应的第一次出现的位置,然后再记录一下每个答案的区间大小,题目要求若区间有多个要求输出最小的那个区间。所以按从1到n的顺序遍历存下的答案即是满足题意的答案了。
复杂度
时间复杂度
代码
#include<bits/stdc++.h> using namespace std; map<int,int>vis; int main() { int n; scanf("%d",&n); int l=n,r=n; int ans=0; int sum=0; for(int i=1; i<=n; i++) { int a; scanf("%d",&a); a=a?1:-1; sum=sum+a; if(vis[sum]!=0) { if(ans<i-vis[sum]) { ans=i-vis[sum]; l=vis[sum]+1; r=i; } } else vis[sum]=i; if(sum==0) { if(ans<i) { ans=i; l=1; r=i; } } } printf("%d %d\n",l,r); return 0; }