Balanced Tunnel

编程入门行业动态更新时间:2024-10-10 08:25:11

Balanced Tunnel

题目

原题链接：1237B Balanced Tunnel
codeforce提交步骤：

假设有一条单向通行的隧道，有一天有 m 辆编号为 1 到 m 的小轿车从这条隧道入口进入然后从出口驶出。每辆车只会经过这个隧道一次。全部的车都以恒定的速度经过隧道。隧道的入口和出口处均设置有交通执法摄像头。从这两个交通执法摄像头，我们可以很清楚地知道每辆车进入和驶出隧道的顺序。没有两辆车会同时进入隧道，并且也没有两辆车会同时驶出隧道。交通法规禁止车辆在隧道中超车。如果车辆 i 在隧道中超了车辆j，那么车辆 i 的车主就会面临罚款。每辆车的车主最多被罚款一次，即使他在隧道中超车多次。我们对车辆 i 超车辆 j 的定义如下：如果车辆 i 晚于车辆 j 进入隧道，并且车辆 i 早于车辆 j 驶出隧道，那么车辆 i 就视为超车了车辆 j。给出车辆按时间顺序进入隧道的顺序和驶出隧道的顺序，请你编程计算有多少个车主会被罚款。（程序运行要求，时间：2sec/空间：256MB）

输入
第一行一个整数 m，表示车辆的个数。
第二行 m 个整数，表示按时间递增的顺序进入隧道的车辆的编号。
每个整数满足大小在 1 到 m 之间并且互不相同。
第三行 m 个整数，表示按时间递增的顺序驶出隧道的车辆的编号。
每个整数满足大小在 1 到 m 之间并且互不相同。
满足 1 <= m <= 10^5。

输出
一个整数，表示被罚款的车主的个数。

样例 1
输入
3
1 2 3
1 2 3
输出
0

样例 2
输入
4
1 3 2 4
4 3 2 1
输出
3

解题思路

根据进出隧道的第一辆车牌号（vector in 和 out元素的第一个）来判断是否超车，如果in=out，即进入时的顺序和出去的顺序一样，说明没有超车，否者就从in中删除out的第一个元素，即最先出隧道的车。如果只有这辆车超车，那么删除该车后，剩下的车的顺序应该保持不变的（中心思路，后面改进版只是设置了一个标记位，用于标记该车的状态是否已经判断，已经判断就跳过）。并将cnt加1，cnt用于统计超车的数量。

例如：
样例 2 
输入
4
1 3 2 4
4 3 2 1
输出
3思路：
进入时顺序（存放在in中）：1 3 2 4
出去顺序（存放在out中）：4 3 2 1
in != out --> 在in中删除值等于out.first:4 的元素，并将cnt++，统计超车的数量
直到in == out结束循环

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;const int N = 1e+5;
vector<int> in, out;int main()
{int m;cin >> m;int num;for (int i = 0; i < m; i++){cin >> num;in.push_back(num);}for (int i = 0; i < m; i++){cin >> num;out.push_back(num);}int cnt = 0;while (in != out){if (in[0] != out[0]){cnt++;}vector<int>::iterator iter = find(in.begin(), in.end(), out[0]);in.erase(iter);out.erase(out.begin());}cout << cnt << endl;return 0;
}

超时，思路没问题，但是在查找和修改容器的过程中，时间复杂度为O(n^2)。修改版（增加了一个存储状态的map sts，用于标记进入隧道的车辆之前是否已在out中访问，防止重复统计），主要思想是用空间换时间。

使用map和deque是为了熟悉这两种容器的操作使用，可以将map换为一个bool类型的数组，deque换为vector。

#include <iostream>
#include <deque>
#include <map>
using namespace std;const int N = 1e+5;
deque<int> in, out;
map<int, bool> visited;int main()
{int m;cin >> m;int num;for (int i = 0; i < m; i++){cin >> num;in.push_back(num);}for (int i = 0; i < m; i++){cin >> num;out.push_back(num);}for (int i = 1; i < m + 1; i++){visited[i] = false;}int cnt = 0;for (int i = 0, j = 0; i < out.size();){if (!visited[in[j]]){visited[out[i]] = true;if (out[i] != in[j])++cnt, ++i;else++i, ++j;}else++j;}cout << cnt << endl;return 0;
}

C语言版：

参考： C语言之const与define区别

#include <stdio.h>
#include <stdlib.h>
#define N 100000int in[N + 10], out[N + 10];
int visited[N + 10];int main()
{int m, cnt = 0, i = 0, j = 0;scanf("%d", &m);for (i = 0; i < m; i++)scanf("%d", &in[i]);for (i = 0; i < m; i++)scanf("%d", &out[i]);for (i = 1; i < m + 1; i++)visited[i] = 0;for (i = 0, j = 0; i < m;){if (!visited[in[j]]){visited[out[i]] = 1;if (out[i] != in[j])++cnt, ++i;else++i, ++j;}else++j;}printf("%d\n", cnt);return 0;
}