Problem: [Usaco2018 Open]Milking Order

Time Limit: 1 Sec Memory Limit: 128 MB

Description

Farmer John的N头奶牛（2≤N≤100），方便起见仍然编号为1…N，正好闲得发慌。因此，她们发展了一个与Farmer John每天早上为她们挤牛奶的时候的排队顺序相关的复杂的社会结构。经过若干周的研究，Farmer John发现这个结构基于两个关键特性。首先，由于奶牛们的社会阶层，某些奶牛会坚持要在其他奶牛之前挤奶，基于她们的社会地位等级。比方说，如果奶牛3有最高的地位，奶牛2位于中等地位，奶牛5是低地位，那么奶牛3会最早挤奶，然后是奶牛2，最后是奶牛5。然后，有些奶牛只允许她们在排队顺序中一个特定的位置挤奶。比方说，奶牛4可能坚持要在所有奶牛中的第二位挤奶。幸运的是，Farmer John总是能够以一种满足所有这些情况的顺序给他的奶牛们挤奶。不幸的是，奶牛1最近生病了，所以Farmer John想要尽早给这头奶牛挤奶，使得她可以回到牛棚获得急需的休息。请帮助Farmer John求出奶牛1可以在挤奶顺序中出现的最早位置。

Input

第一行包含N，M（1≤M<N），和K（1≤K<N）
表示Farmer John有N头奶牛，其中M头形成了社会阶层，K头需要在挤奶顺序中处于一个特定的位置。
下一行包含MM个不同的整数mimi（1≤mi≤N）。
在这一行出现的奶牛必须以与她们在这行出现的顺序相同的顺序进行挤奶。
下面K行，每行包含两个整数ci（1≤ci≤N）和pi（1≤pi≤N），表示奶牛cici一定要在第pi位进行挤奶。
输入数据保证在这些限制之下，Farmer John能够建立一个符合要求的挤奶顺序。

Output

输出奶牛1可以在挤奶顺序中出现的最早位置。

Sample Input

6 3 2
4 5 6
5 3
3 1

Sample Output

4
HINT
在这个例子中，Farmer John有六头奶牛，其中奶牛1生病了。他的挤奶顺序应该为奶牛4在奶牛5之前，奶牛5在奶牛6之前。此外，Farmer John必须要第一个给奶牛3挤奶，第三个给奶牛5挤奶。FJ必须第一个给奶牛3挤奶，由于奶牛4必须要在奶牛5之前，奶牛4一定是第二个挤奶的，然后奶牛5第三个。于是，奶牛1最早在挤奶顺序中出现的位置是第四个。
代码如下

#include <iostream>
#include <algorithm>
using namespace std;
  
bool usedCow[100];
bool usedPos[100];
int pos[100];
  
  
int nCows, M, nFixed;
  
int ord[100];
  
int cFixed[101];
int pFixed[101];
  
bool works()
{
    for(int i=0;i<nCows;i++)
        usedCow[i] = usedPos[i] = 0;
    for(int i=0;i<nFixed;i++)
    {
        if(usedCow[cFixed[i]] && pos[cFixed[i]] == pFixed[i]) continue;
        if(usedCow[cFixed[i]]) return 0;
        if(usedPos[pFixed[i]]) return 0;
        usedCow[cFixed[i]] = 1;
        usedPos[pFixed[i]] = 1;
        pos[cFixed[i]] = pFixed[i];
    }
    int j = 0;
    for(int i=0;i<M;i++)
    {
        int cow = ord[i];
        if(usedCow[cow])
        {
            if(j > pos[cow]) return 0;
            j = pos[cow];
            continue;
        }
        while(usedPos[j])
        {
            j++;
            if(j == nCows)
                return 0;
        }
        usedPos[j] = 1;
        pos[cow] = j;
    }
    return 1;
}
  
int main()
{
    cin >> nCows >> M >> nFixed;
    for(int i=0;i<M;i++)
    {
        cin >> ord[i];
        ord[i]--;
    }
    for(int i=0;i<nFixed;i++)
    {
        cin >> cFixed[i] >> pFixed[i];
        cFixed[i]--, pFixed[i]--;
    }
    nFixed++;
    for(int i=0;i<nCows;i++)
    {
        cFixed[nFixed-1] = 0;
        pFixed[nFixed-1] = i;
        if(works())
        {
            cout << i+1 << '
';
            return 0;
        }
    }
}