挤奶顺序

题目

链接：1726. 挤奶顺序 - AcWing题库

Farmer John 有 N 头奶牛，编号为 1…N。

他每天都要给他的奶牛们挤奶。

奶牛的社会结构非常复杂，其结构有两个关键特性。

首先，有 M 头奶牛的地位等级分明，按照地位越高越早挤奶的规则，这些奶牛的相对挤奶顺序是固定的。

此外，有 K 头奶牛的具体挤奶顺序也是固定的，比方说，奶牛 4 必须在所有奶牛中的第二位挤奶。

幸运的是，Farmer John 总是能够以一种满足所有这些情况的顺序给他的奶牛们挤奶。

不幸的是，奶牛 1 最近生病了，所以 Farmer John 想要尽早给这头奶牛挤奶，使得她可以回到牛棚获得急需的休息。

请帮助 Farmer John 求出奶牛 1 可以在挤奶顺序中出现的最早位置。

输入格式
第一行包含 N，M，K，表示 Farmer John 有 N 头奶牛，其中 M 头形成了社会阶层，K 头需要在挤奶顺序中处于一个特定的位置。

下一行包含 M 个不同的整数 mi。在这一行出现的奶牛必须以与她们在这行出现的顺序相同的顺序进行挤奶。

下面 K 行，每行包含两个整数 ci 和 pi，表示奶牛 ci 一定要在第 pi 位进行挤奶。

输入数据保证在这些限制之下，Farmer John 能够建立一个符合要求的挤奶顺序。

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

数据范围
2≤N≤100,
1≤M,K<N,
1≤mi,ci,pi≤N

import java.util.*;


public class Main {
    static int N = 100010;
    static int n, m, k;
    static int[] a = new int[110];
    static int[] c = new int[110];
    static int[] f = new int[110];
    public static void work(int l, int r, int q)
    {
        while(r >= l)
        {
            if(c[q] == -1)
            {
                c[q] = a[r];
                r --;
            }
            q --;
        }
    }
    public static void main(String[] args) {
        Scanner inScanner = new Scanner(System.in);
        n = inScanner.nextInt();
        m = inScanner.nextInt();
        k = inScanner.nextInt();
        boolean t = false;
        Arrays.fill(c, -1);
        for(int i = 1; i <= m; i ++)
        {
            a[i] = inScanner.nextInt();
            if(a[i] == 1)
                t = true;
        }
        for(int i = 1; i <= k; i ++)
        {
            int ci, pi;
            ci = inScanner.nextInt();
            pi = inScanner.nextInt();
            c[pi] = ci;
            f[ci] = pi;
        }
        int pre = 0;
        for(int i = 1; i <= m; i ++)
        {
            if(f[a[i]] != 0)
            {
                work(pre + 1, i - 1, f[a[i]] - 1);
                pre = i;
            }
        }
        inScanner.close();
        if(t)
        {
            int j = f[a[pre]] + 1;
            int i = pre + 1;
            while(i <= m && j <= n)
            {
                if(c[j] == -1)
                {
                    c[j] = a[i];
                    i ++;
                }
                j ++;
            }
            for(i = 1; i <= n; i ++)
            {
                if(c[i] == 1)
                {
                    System.out.println(i);
                    break;
                }
            }
        }
        else
        {
            for(int i = 1; i <= n; i ++)
            {
                if(c[i] == -1)
                {
                    System.out.println(i);
                    break;
                }
            }
        }
    }
}