C++算法题（不超过普及难度）

Question

农夫约翰有N头牛（2≤N≤105）。每头牛的品种不是根西岛就是荷尔斯泰因。通常情况下，奶牛排成一排，按顺序编号为1…N。

在一天的过程中，每头牛都会写下一份奶牛名单。具体而言，奶牛i的列表包含了从自己（奶牛i）到奶牛Ei（i≤Ei≤N）的奶牛范围。

FJ最近发现，每种奶牛都有一个不同的领导者。FJ不知道领头人是谁，但他知道每个领头人都必须有一份名单，其中包括他们品种的所有奶牛，或其他品种的领头人（或两者）。

帮助FJ计算可能成为领导者的奶牛对数。保证至少有一个可能的对。

INPUT FORMAT（输入来自终端/stdin）：

第一行包含N。

第二行包含长度为N的字符串，第i个字符表示第i头牛的品种（G表示根西岛，H表示荷尔斯泰因）。保证至少有一个根西岛和一个荷尔斯泰因岛。

第三行包含E1…EN。

OUTPUT FORMAT（输出格式）（将输出打印到终端/标准输出）：

输出可能的引线对数。

样本输入：
4
GHHG
2 4 3 4
样本输出：
1
唯一有效的一对是（1,2）。奶牛1的列表中包含其他品种的领头羊（奶牛2）。奶牛2的列表中包含了她的品种（荷斯坦）的所有奶牛。
其他配对无效。例如，（2，4）是无效的，因为奶牛4的列表中不包含其他品种的领头羊，也不包含其品种的所有奶牛。
样本输入：
3
GGH
2 3 3
样本输出：
2
有两个有效的配对，（1,3）和（2,3）。
数据：
输入3-5:N≤100
输入6-10:N≤3000
输入11-17：无附加约束。

希望有人帮忙给出代码，复杂度最好为O(n)的，谢谢！

Answer 1

for循环遍历，判断是否满足条件
麻烦的是第一头G牛（或者H牛）的判断，第一头G牛判断完毕后，后面的G牛只需要判断是否满足第二个条件（即名单中包含H牛的头领）。
代码如下：

#include <iostream>
using namespace std;
int main()
{
    int E[110] = { 0 }; //Ei
    char type[110] = { 0 };//品种
    int nmb = 0; //记录可能的对数
    int n;
    cin >> n; //输入n
    cin >> type;
    for (int i = 0; i < n; i++)
        cin >> E[i];

    //找到第一头G牛和第一头H牛的位置
    int pos_g = -1, pos_h = -1;
    for (int i = 0; i < n; i++)
    {
        if (pos_g != -1 && pos_h != -1)
            break;
        if (pos_g == -1 && type[i] == 'G')
            pos_g = i + 1;
        if (pos_h == -1 && type[i] == 'H')
            pos_h = i + 1;
    }

    //判断第一头G牛能否成为头领
    int flag_g = 1;
    //1.判断名单中是否包含所有G品种的牛，因为是第一头，所以只向后判断
    for (int i = E[pos_g - 1] + 1; i <= n; i++)
    {
        if (type[i - 1] == 'G')
        {
            flag_g = 0;//表示不成立
            break;
        }
    }
    //2.如果1不成立，再判断第二个条件，是否包含了H牛的头领
    if (flag_g == 0)
    {
        for (int i = pos_g + 1; i <= E[pos_g]; i++)//遍历G牛的名单
        {
            if (type[i - 1] == 'H')//判断H牛
            {
                //1.判断I牛的列表中是否包含第一头G牛，这个条件明显不成立，因为for循环中i的起始值从pos_g+1开始
                if (pos_g > i && pos_g <= E[i - 1])
                    nmb++;
                else
                {
                    //2.判断I牛是否包含了所有H牛
                    int flag_h = 1;
                    for (int j = 1; j < i; j++)
                    {
                        if (type[j - 1] == 'H')
                        {
                            flag_h = 0;
                            break;
                        }
                    }
                    if (flag_h == 1) //判断后面的
                    {
                        for (int j = E[i - 1] + 1; j <= n; j++)
                        {
                            if (type[j - 1] == 'H')
                            {
                                flag_h = 0;
                                break;
                            }
                        }
                    }
                    if (flag_h == 1)
                        nmb++; //满足条件，可以成为1对
                }
            }
        }
    }
    else
    {
        //1成立，包含了所有G牛，遍历所有的H牛
        for (int i = pos_h; i <= n; i++)
        {
            if (type[i - 1] == 'G') //过滤所有的G牛
                continue;
            //1.判断pos_g是否再i牛的名单中
            if (pos_g > i && pos_g <= E[i - 1]) 
                nmb++;
            else
            {
                //2.判断i牛是否包含了所有的H牛
                if (i == pos_h)//如果i>pos_h，则明显不满足条件，所以，这里只判断i==pos_h的情况
                {
                    //i是第一头H牛，只需要向后判断
                    int flag_h = 1;
                    for (int j = E[i - 1] + 1; j <= n; j++)
                    {
                        if (type[j - 1] == 'H')
                        {
                            flag_h = 0;
                            break;
                        }
                    }
                    if (flag_h == 1)
                        nmb++;
                }
            }
        }

    }





    //第1头G牛判断完毕后，判断后面的G牛，后面的G牛名单永远不会满足第1个条件，所以只需要判断条件2是否满足即可
    while (1)
    {
        pos_g++;
        //找到g牛
        for (; pos_g <= n; pos_g++)
        {
            if (type[pos_g-1] == 'G')
                break;
        }
        if (pos_g > n)
            break;
        
        //遍历名单中的所有H牛
        for (int i = pos_g + 1; i <= E[pos_g]; i++)//遍历G牛的名单
        {
            if (type[i - 1] == 'H')//判断H牛
            {
                //1.判断I牛的列表中是否包含第一头G牛，这个条件明显不成立，因为for循环中i的起始值从pos_g+1开始
                if (pos_g > i && pos_g <= E[i - 1])
                    nmb++;
                else
                {
                    //2.判断I牛是否包含了所有H牛
                    int flag_h = 1;
                    for (int j = 1; j < i; j++)
                    {
                        if (type[j - 1] == 'H')
                        {
                            flag_h = 0;
                            break;
                        }
                    }
                    if (flag_h == 1) //判断后面的
                    {
                        for (int j = E[i - 1] + 1; j <= n; j++)
                        {
                            if (type[j - 1] == 'H')
                            {
                                flag_h = 0;
                                break;
                            }
                        }
                    }
                    if (flag_h == 1)
                        nmb++; //满足条件，可以成为1对
                }
            }
        }
    }


    cout << nmb;
    return 0;
}