分析
本题可以简单的描述一下:
给定相对顺序数组A要求把A中的元素填到另一个数组B中空闲的位置,要求A中元素在B中仍然保持数组A中的相对顺序,在此规则下求出元素1最靠前合理出现的位置。
分三种情况来考虑:
-
元素1已经事先在B数组中确定位置
那么不需要后面的繁杂分析了,直接返回即可。根据题目的意思也可以看出来这种特殊情况没有任何含金量,考察的不是这个。 -
元素1事先没在B数组中确定位置,并且元素1不在顺序数组A中出现
按照贪心规则从后向前,对A和B分别用双指针进行“填空”。最后从前向后扫描一遍把A中元素填到B中之后的数组,第一个没有被填的位置,即为答案。 -
元素1事先没在B数组中确定位置,并且元素1在顺序数组A中出现
仍然按照贪心规则,以元素1在数组A中出现的位置记为idx作为分界点,考虑idx前后两段怎么填入B中。
我们让idx后面的元素尽可能的靠后,让idx前面的元素尽可能的靠前,最后从前向后扫描一遍把A中元素填到B中之后的数组,第一个没有被填的位置,即为答案。
为了用一种写法实现后两种情况,先从后向前填空,遇到元素1跳出,而后从前向后填即可。
注意:这里为什么要先进行从后向前,后进行从前向后的顺序呢?
其实对于情况3来说,直接从前向后填就可以了,第一次填入元素1的位置一定是答案。但是如果元素1不在A中,一定要从后向前填,最后第一个空位置才是答案。
而按照后->前,前->后的顺序可以保证对于情况2、3一定都是正确的。当元素1不在A中时,第二次填空(前->后的填法)基本上没有任何影响,什么都没干。
时间复杂度:$O(n)$
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int nums[N], a[N];
int st[N];
int main()
{
int n, m, k;
cin >> n >> m >> k;
for(int i = 0; i < m; i++) {
cin >> a[i];
}
int x, y;
while(k--) {
cin >> x >> y;
if(x == 1) {
cout << y << endl;
return 0;
}
nums[y] = x;
st[x] = y;
}
int i = n, j = m - 1;
while(i && j >= 0) {
if(!nums[i]) {
while(st[a[j]]) {
i = st[a[j--]] - 1;
}
while(i && nums[i]) i--;
if(a[j] == 1) break;
st[a[j]] = i;
nums[i] = a[j];
j--, i--;
} else {
i--;
}
}
i = 1, j = 0;
while(i <= n && j < m) {
if(!nums[i]) {
while(st[a[j]]) {
i = st[a[j++]] + 1;
}
while(i <= n && nums[i]) i++;
if(a[j] == 1) {
cout << i << endl;
return 0;
}
st[a[j]] = i;
nums[i] = a[j];
i++, j++;
} else {
i++;
}
}
int ans = 0;
for(int i = 1; i <= n; i++) {
if(nums[i] == 0) {
ans = i;
break;
}
}
cout << ans << endl;
return 0;
}