【分类讨论+思维】AcWing1726.挤奶顺序 USACO 2018 US Open Contest Bronze

原题链接

Farmer John 有 N 头奶牛，编号为 1…N。
他每天都要给他的奶牛们挤奶。
奶牛的社会结构非常复杂，其结构有两个关键特性。
首先，有 M 头奶牛的地位等级分明，按照地位越高越早挤奶的规则，这些奶牛的相对挤奶顺序是固定的。
此外，有 K 头奶牛的具体挤奶顺序也是固定的，比如，奶牛 4 必须在所有奶牛中的第二位挤奶。
幸运的是，Farmer John 总是能够以一种满足所有这些情况的顺序给他的奶牛们挤奶。
不幸的是，奶牛 1 最近生病了，所以 Farmer John 想要尽早给这头奶牛挤奶，使得她可以回到牛棚休息。
请帮助 Farmer John 求出奶牛 1 可以在挤奶顺序中出现的最早位置。

题意

一共有n头奶牛，并且有两个约束：第一个约束是给出若干个奶牛的顺序，就是在最后的摆放中一定其中给出这些的约束奶牛顺序一定是这样的，可以不连续；第二个约束是给出若干个奶牛，这些奶牛必须放在固定位置上
求：编号为1的奶牛最早能放在哪个地方？

思路

这是一道分类讨论题，在AcWing里面是普通题，一开始没能做出来...
1）最简单的情况，第二个约束位置的时候，已经给出1了，那么此时直接输出即可

2）第一个约束顺序的时候，其中有1，那么就去找约束顺序1前面看有没有被固定住的，比如4->1，4被固定在第3个位置，那么就指针跳到3，从3往后看能不能放1，如果没有被固定住的，那么就直接摆放顺序在1前面的，注意：被固定位置放了的不能再放，一个while循环搞定.这种思想是从前往后

for (int i = 1, j = 1; i <= m; i ++ )
{
    while (st[j]) j ++ ;
    if (p[q[i]] != -1) j = p[q[i]];
    else
    {
        if (q[i] == 1)
        {
            cout << j << endl;
            return 0;
        }
        st[j] = true;
        j ++ ;
    }
}

3）最后一种情况，约束顺序和约束位置都没有1，那么我们考虑一种，从后往前摆放，那么最后剩下的就是奶牛1的位置,最后从前往后看看哪里有空位，那就是1的位置

for (int i = m, j = n; i; i -- )
{
    while (st[j]) j -- ;
    if (p[q[i]] != -1) j = p[q[i]];
    else
    {
        st[j] = true;
        j -- ;
    }
}
for (int i = 1; i <= n; i ++ )
    if (!st[i])
    {
        cout << i << endl;
        return 0;
    }

代码

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

using namespace std;

const int N = 110;

int n, m, k;
int q[N];
int p[N];
bool st[N];

int main()
{
    cin >> n >> m >> k;

    bool flag = false;
    for (int i = 1; i <= m; i ++ )
    {
        cin >> q[i];
        if (q[i] == 1) flag = true;
    }

    memset(p, -1, sizeof p);
    for (int i = 0; i < k; i ++ )
    {
        int a, b;
        cin >> a >> b;
        if (a == 1)
        {
            cout << b << endl;
            return 0;
        }
        p[a] = b;
        st[b] = true;
    }

    if (flag)
    {
        for (int i = 1, j = 1; i <= m; i ++ )
        {
            while (st[j]) j ++ ;
            if (p[q[i]] != -1) j = p[q[i]];
            else
            {
                if (q[i] == 1)
                {
                    cout << j << endl;
                    return 0;
                }
                st[j] = true;
                j ++ ;
            }
        }
    }
    else
    {
        for (int i = m, j = n; i; i -- )
        {
            while (st[j]) j -- ;
            if (p[q[i]] != -1) j = p[q[i]];
            else
            {
                st[j] = true;
                j -- ;
            }
        }

        for (int i = 1; i <= n; i ++ )
            if (!st[i])
            {
                cout << i << endl;
                return 0;
            }
    }

    return 0;
}
//From yxc