Codeforces --- Balanced Tunnel
见链接http://codeforces.com/contest/1237/problem/B。
这道题的本质是找递增序列中出现的非递增数的数目。如果未发生超车情况,则进入的车在出去的时候,应该是一个递增的序列。
于是可以用一个pos[x]数组来记录标号为i的车出去时候的顺序,这样,当我们按照进入时候的顺序进行遍历时,如果车发生过超车现象,那么肯定有某辆入序靠后的车其先出去了,也就是pos[x]的值小于之前的最大值。以样例1为例。
进入顺序: 1 2 3 4 5
进入时车的标号顺序: 3 5 2 1 4
出去的顺序数组: 2 4 3 5 1
出去时车的标号顺序: 4 3 2 5 1
显然,按照35214的顺序遍历的时候,只需要每次保存遍历到当前位置时的最大出去的序号值,就可以判断出是否有超车了,代码如下,时间复杂度为O(n)。当然,这道题还可以采取求逆序对的方式来求解,复杂度为O(nlogn)。
#include
using namespace std;
static const int MAX = ;
int arr[MAX];
int pos[MAX];
int main(){
int n;
scanf("%d", &n);
// read arr
for(int i=;i<=n;i++){
scanf("%d", &arr\[i\]);
}
// construct pos
int num;
for(int i=;i<=n;i++){
scanf("%d", &num);
pos\[num\] = i;
}
// solve
int sum = ;
int tmp = ;
for(int i=;i<=n;i++){
tmp = max(tmp, pos\[arr\[i\]\]);
if(pos\[arr\[i\]\]<tmp){
sum++;
}
}
printf("%d\\n", sum);
return ;
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章