艰难的选择

一月24日

洛谷P1114

• Description

  Yzx已经当过多次“媒人”了。他因此获得了许多经验。例如，距Yzx观察，身高相近的人似乎比 较合得来。
  Yzx在学校策划了一次大型的“非常男女”配对活动。对于这次活动的参与者，Yzx有自己独特的选择方式。他希望能选择男女人数相等且身高都很接近的一些人。这种选择方式实现起来很简单，他让学校的所有人按照身高排成一排，然后从中选出连续的若干个人，使得这些人中男女人数相等。Yzx当然希望他能选出的人越多越好，请告诉他最多可以选出多少人来。

• Input

  第一行有一个正整数n，代表学校的人数。
  第二行有n个用空格隔开的数，这些数只能是0或1，其中，0代表一个男生，1代表一个女生。

• Output

  一个非负整数，表示最长的一段男女人数相等的子序列长度（如果不存在男女人数相等的子序列输出0）。

• Sample Input

  9
  0 1 0 0 0 1 1 0 0

• Sample Output

6

• Data Constraint

  30%的数据，n<=100。

  50%的数据，n<=1000。

  100%的数据，n<=100000。

• Solution

1. 我首先想到的是直接\(O(n^2)\)的两个for循环直接暴力。然后我就直接这么做了。。。傻子都知道会超时。然后我拿了60分滚蛋。

#include<cstdio>
#include<algorithm>
using namespace std;

int n,a[100002],maxn;

int main()
{
    scanf("%d",&n);
    for(int i=1,temp;i<=n;i++)
    {
        scanf("%d",&temp);
        if(temp==0) --temp;
        a[i]=a[i-1]+temp;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
            if(a[i]-a[j-1]==0)
                maxn=max(maxn,i-j+1);
    printf("%d",maxn);
    return 0;
}

1. 赛后，我学到了一个神奇优化。在纪中OJ上80分，洛谷90分，洛谷开O2可以AC。（杨逸舸版权所有）

#include<cstdio>
#include<algorithm>
using namespace std;

int n,a[100002],maxn;

int main()
{
    scanf("%d",&n);
    for(int i=1,temp;i<=n;i++)
    {
        scanf("%d",&temp);
        if(temp==0) --temp;
        a[i]=a[i-1]+temp;
        if(a[i]==0) maxn=i;
    }
    for(int i=maxn+1;i<=n;i++)
        for(int j=1;j<=i-maxn;j++)
            if(a[i]-a[j-1]==0)
                maxn=max(maxn,i-j+1);
    printf("%d",maxn);
    return 0;
}

1. 这种方法还是我自己比赛的时候yy的，我想100000 不就是要一个\(O(n \log n)\)的方法吗。于是我想到了二分答案然后尺取法判断，结果打完后发现这样做是错的，反例就是maxn==n。

2. 某大佬思路：引入相对差的概念。即a[i]表示第i个位置男生人数-女生人数的差值。那么差值相等的两个位置之间的人数是满足男女相等的。从此统计l[a[i]]和r[a[i]]。特别要注意的是a[0]=0统计的时候要把0的位置当做差为0的起点。打了一次结果只有70于是放弃。

3. 最后的最后，我把男生设为1，女生设为-1。先用a数组存一下前缀和，再用l表示l[i]\(=\)a[i]时的最小的j然后一遍\(O(n)\)处理就可以了。

#include<cstdio>
#include<algorithm>
using namespace std;

int n,a[200002],maxn,l[200004];

int main()
{
    scanf("%d",&n);
    for(int i=1,temp;i<=n;i++)
    {
        scanf("%d",&temp);
        if(temp==0) temp=-1;
        a[i]=a[i-1]+temp;
    }
    for(int i=1;i<=n;i++)
    {
        if(!a[i])
        {
            maxn=max(maxn,i);
            continue;
        }
        if(l[a[i]+n])
            maxn=max(maxn,i-l[a[i]+n]);
        if(!l[a[i]+n])
            l[a[i]+n]=i;
    }
    printf("%d",maxn);
    return 0;
}

真是个艰难的选择啊c

• 考点

  略 我也不知道

艰难的选择

原文：https://www.cnblogs.com/mocking-jimmy/p/10349662.html