Codeforces--Balanced Tunnel

问题重述

Codeforces --- Balanced Tunnel

见链接http://codeforces.com/contest/1237/problem/B。

Solve

这道题的本质是找递增序列中出现的非递增数的数目。如果未发生超车情况，则进入的车在出去的时候，应该是一个递增的序列。

于是可以用一个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<bits/stdc++.h>

using namespace std;

static const int MAX = 1000000;

int arr[MAX];
int pos[MAX];

int main(){
    int n;
    scanf("%d", &n);

    // read arr
    for(int i=1;i<=n;i++){
        scanf("%d", &arr[i]);
    }
    // construct pos
    int num;
    for(int i=1;i<=n;i++){
        scanf("%d", &num);
        pos[num] = i;
    }    

    // solve
    int sum = 0;
    int tmp = 0;
    for(int i=1;i<=n;i++){
        tmp = max(tmp, pos[arr[i]]);
        if(pos[arr[i]]<tmp){
            sum++;
        }
    }
    printf("%d
", sum);
    return 0;
}