Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

Codeforces--Balanced Tunnel

守功 2019-10-19 00:29:00 阅读数:97 评论数:0 点赞数:0 收藏数:0

问题重述

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=;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 ;
 }

 

   

版权声明
本文为[守功]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/sgatbl/p/11701504.html