huring
0%

51nod-2494-最长配对

Posted on In

题目：

小b有一个01序列，她想找到一个最长的区间使得这个区间的01能两两配对，即0的个数和1的个数相等。求最长区间的长度。

输入

第一行一个正整数n，表示数组长度，其中0＜n≤50000；
第二行n个0或1，以空格隔开。

输出

输出一个数，表示最长区间的长度

输入样例

1
2
3
0 1 0

输出样例

1
2

解法：

将0当做-1处理，处理前缀和，记录前缀和相同的位置，计算出前缀和相同位置的最长距离。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<stdio.h>
#include<vector>
#include<cstring>
using namespace std;
int a[1000010];
vector<int> p[2000010];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i = 1; i <=n; i++)
        scanf("%d", &a[i]);
    int sum = 0;
    int Max = -999999999;
    int Min = 999999999;
    p[1000000].push_back(0);
    for(int i = 1; i <= n; i++)
    {
        if(a[i] == 0)
            sum++;
        else
            sum--;
        Max = max(sum, Max);
        Min = min(sum, Min);
        p[sum + 1000000].push_back(i); 
    }
    int ans = 0;
    
    //printf("%d %d\n", Min, Max);
    for(int i = Min + 1000000; i <= Max + 1000000; i++)
    {
        ans = max(p[i][p[i].size() - 1]-p[i][0], ans);
    }
    printf("%d\n", ans);
}