Luobuyu's Blog

0%

1726.挤奶顺序

发表于 分类于 ， 热度： ℃ 评论：
本文字数： 2.2k 阅读时长 ≈ 2 分钟
情况比较多，没考虑从前往后排。

1726. 挤奶顺序

题目描述：

Farmer John 有 N 头奶牛，编号为 $ 1\cdots N $ 。

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

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

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

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

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

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

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

输入格式

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

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

下面 KK 行，每行包含两个整数 $ c_i $ 和 $ p_i $ ，表示奶牛 $ c_i $ 一定要在第 $ p_i $ 位进行挤奶。

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

输出格式

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

数据范围

输入样例：

1
2
3
4
6 3 2
4 5 6
5 3
3 1

输出样例：

1
4

题解：

首先需要分类考虑一下。

  • 如果 1 直接出现在了 k 中，那么直接输出。
  • 如果 1 出现在了 m 中，那么 1 如果要在最前的话，就需要贪心的把 m 从前往后填，填的时候注意如果 m 中的数也在 k 中是已经排好的，那么就要从这一段再往后，一直到找到 1 为止。
  • 如果 1 在 m 和 k 中都没有出现，那么 1 如果在最前的话，就需要把 m 中的数字从后往前贪心的排，同样，如果 m 中的数字在 k 中是已经排好的，那么就要从这一段再往前，一直填完为止，然后找到最前面的一个空位，填入 1 。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e3 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;
int a[maxn];
int order[maxn]; // 记录每个数字填入到了哪个位置，这样方便的找前一个或后一个位置
bool st[maxn];
int main()
{
// #define COMP_DATA
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> k;
    bool flag = false;
    for (int i = 1; i <= m; i++)
    {
        cin >> a[i];
        if (a[i] == 1)
        {
            flag = true;
        }
    }
    for (int i = 1, x, y; i <= k; i++)
    {
        cin >> x >> y;
        order[x] = y;
        st[y] = true;
        if (x == 1)
        {
            cout << y << endl;
            return 0;
        }
    }

    if (flag)
    {
        // 1在m中，从前往后摆放
        int index = 1;
        for (int i = 1; i <= m; i++)
        {
            while (st[index])
                index++;
            // 这个m中的a[i]也在k中
            if (order[a[i]] != 0)
            {
                index = order[a[i]];
            }
            else
            {
                order[a[i]] = index;
                st[index] = true;
                if (a[i] == 1)
                {
                    cout << index << endl;
                    return 0;
                }
            }
        }
    }
    else
    {
        int index = n;
        for (int i = m; i >= 1; i--)
        {
            while (st[index])
                index--;
            if (order[a[i]] != 0)
            {
                index = order[a[i]];
            }
            else
            {
                st[index] = true;
                order[a[i]] = index;
            }
        }

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