约翰农夫的牛领袖问题

Question

1.领袖
FJ(约翰农夫，在USACO中很常见的角色)有n头牛(n满足2<=n&&n<=10^5),每头牛都有一个品种:要么是G,要么是H。
一般情况下这些牛排成一排，将其编号为1~n.
有一天，每一头牛都写下了一份名单。具体来说，第i只牛的名单中包括从i开始到e[ i]的所有牛(包括e[ i],e[ i]满足i<=e[ i]&&e[ i]<n)
FJ发现每种牛都有一个领袖，但他不知道哪头牛是领袖，只知道每个领袖的名单中必然有与他相同品种的所有牛，或者另一种牛的领袖。
请帮助FJ计算牛群领袖的对数。数据保证有唯一解。

输入格式（依照惯例，输入来自终端/标准输入）：

第一行包含一个整数n.
第二行包含一个长度为n的字符串(只包括G和H两种字符)，其中第i个字符表示第i头牛的品种（G 表示根西岛，H 表示荷斯坦）。保证至少有一个G和一个H。
第三行包含一个长度为n的正整数序列E,其中第i个数表示E[ i]的值.

输出格式（直接输出）：
一行一个整数，表示可能的领导对数。

输入样例1:
4
GHHG
2 4 3 4
复制代码

输出样例1:
1
复制代码

样例解释：只有(1,2)是可行的方案因为第1头牛的名单中包括另外一族的奶牛首领(第2头)。
没有其他可行解。例如(2,4)就不可行，因为第4头牛的名单不满足前述条件。

输入样例2：
3
GGH
2 3 3
复制代码

输出样例2：
2
复制代码

样例解释：(1,3)和(2,3)是唯二可行解。

数据规模限制:
#1#3满足 2<=n<=100
#4#10满足 2<=n<=3000
#11~#17无额外要求

Answer 1

C++代码如下：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
int e[N];
char str[N];

int main()
{
cin >> n;
cin >> str + 1;
for (int i = 1; i <= n; i ++) cin >> e[i];
int l = 1, r = n, res = 0;
while (l <= r)
{
    int mid = (l + r) >> 1;
    int k = mid;
    for (int i = mid; i; i = e[i])
        if (e[i] >= k) k = i;
    if (str[k] == 'G')
    {
        res = k;
        l = mid + 1;
    }
    else r = mid - 1;
}

cout << res << endl;

return 0;}

C语言代码如下：

#include <stdio.h>
#include <string.h>

const int N = 100010;

int n;
int e[N];
char str[N];

int main()
{
scanf("%d", &n);
scanf("%s", str + 1);
for (int i = 1; i <= n; i ++) scanf("%d", &e[i]);int l = 1, r = n, res = 0;
while (l <= r)
{
    int mid = (l + r) >> 1;
    int k = mid;
    for (int i = mid; i; i = e[i])
        if (e[i] >= k) k = i;
    if (str[k] == 'G')
    {
        res = k;
        l = mid + 1;
    }
    else r = mid - 1;
}

printf("%d\n", res);

return 0;
}