已知各个牛相对顺序和绝对顺序,求牛1的位置
分类三种情况
情况1:已知牛1的绝对位置 直接输出
情况2:已知牛1的相对位置 那么先放相对位置在牛1前面的牛 再放牛1
情况3:不知道的牛的位置
#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;//发现了牛1 标记为情况2 } 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)//情况2 { for (int i = 1, j = 1; i <= m; i ++ )//m是相对牛的数量 { while (st[j]) j ++ ;//找空位,j是一直是空位置指针 if (p[q[i]] != -1) j = p[q[i]];//如果相对牛的位置确定下来(说明还是绝对牛)且这个牛不是牛1,说明牛1还在后面,j从这个位置开始,i取下一个相对牛 else { if (q[i] == 1) { //如果这个相对牛是牛一,直接输出这个空位置 cout << j << endl; return 0; } st[j] = true;//不是牛1,又没确定下来,就把这个位置设置为真 j ++ ; } } } else { for (int i = m, j = n; i; i -- )//先把绝对牛有多少是多少全部放到后面 那么第一个空位置就是牛1了 { while (st[j]) 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;