P1114”非常男女“ 前缀和+双指针

· · 个人记录

前缀和+双指针

这道题第一眼看，大概就知道可能和前缀和有关~（才不是看了算法标签）

这是因为

#### 前缀和可以清楚的表示男女之间连续的数量差的关系。

也正是因为要用前缀和，我们将女生的值定为-1，男生的值为1；

然后我们使用结构体来存储每次输入的信息，结构体中一个值表示男女数，一个表示排序前的位置。然后对男女数量使用前缀和。这样寻找符合要求的区间的时候直接拍个序，再搜一下就好了。

struct Place{
    int num,pos;
};

有两种情况表示是符合要求的[l,r]区间。

第一种：

当l位置的前缀和的值和r位置的前缀和的值相等时，说明此区间(l,r]内的男女人数一样，所以一顿操作之后前缀和的值没有改变。

对于这种情况我们只需要对前缀和的值排个序，然后每次找出“相同前缀和内的最大区间长度”来更新我们的结果。

这里我们可以使用双指针算法（其实也不完全是双指针），即每次找到一个不同的值固定i指针，让j指针往后移动来更新最长区间，当j指针的值和i指针不一样的时候，i指针直接移动到j指针的当前位置，然后再继续搜索。这样算下来，总共只需要扫一遍整个区间就能找出答案；

    for(i=1; i<=n; i++) {
        for(j=i+1; j<=n&&arr[j].num==arr[i].num; j++) {
            res=max(res,arr[i].pos-arr[j].pos);
            if(arr[i].num==0) res=max(res,arr[i].pos);
        }
        i=j-1;
    }

第二种

（这一种我一开始漏了导致听取wa声一片） 当某个位置的前缀和的值为0的时候说明从一开始到这个位置就是符合要求的区间，因此我们可以对于每个前缀和是0的位置都更新一下最大区间。

当然，在写排序函数的时候我们可以按照前缀和的值从小到大排序，相同的值位置从大到小排序，这样当扫到0的时候直接更新的一个就行了；

这是排序函数：

bool rule(Place A,Place B) {
    if(A.num!=B.num) return A.num<B.num;
    return A.pos>B.pos;
}

下面附上AC代码：

#include<bits/stdc++.h>
#define MAXN 100050
using namespace std;
//结构体存储前缀和的值和排序前的位置 
struct Place {
    int num,pos;
};
//人数，arr来存储，p是输入的值，res最后的结果，i和j两个搜索的指针。 
int n;
Place arr[MAXN];
int p,res=0;
int i,j;

//按照前缀和的值从小到大，相同的值按原来的位置从大到小排序 
bool rule(Place A,Place B) {
    if(A.num!=B.num) return A.num<B.num;
    return A.pos>B.pos;
}

int main() { 
    ios::sync_with_stdio(false);
    cin >> n;

    for(int i=1; i<=n; i++) {
        cin >> p;
        if(p==1) arr[i].num=1;  //如果是男生就加上1 
        else arr[i].num=-1;     //如果是女生就减去1 
        if(i!=1) arr[i].num+=arr[i-1].num;  //进行前缀和 
        arr[i].pos=i;           //记录原来的位置 
    }
    //按照规则排个序 
    sort(arr+1,arr+1+n,rule);
    //整个区间找一遍 
    for(i=1; i<=n; i++) { //两个指针i表示每个值前面固定的指针，j表示往后查找的指针； 
        for(j=i+1; j<=n&&arr[j].num==arr[i].num; j++) { 
            res=max(res,arr[i].pos-arr[j].pos); //当i和j位置的前缀和值一样，更新最大长度 
            if(arr[i].num==0) res=max(res,arr[i].pos);  //特判，当此位置的前缀和是0的时候，从头到此位置就是最大长度，更新结果 
        }
        i=j-1; //当i和j的值不一样的时候，将i挪到j的位置上，j继续寻找 
    }
    cout << res;   
    return 0;
}