超车问题
假设有一条单向通行的隧道，有一天有m辆编号为1到m的小轿车从这条隧道入口进入然后从出口驶出。每辆车只会经过这个隧道一次。全部的车都以恒定的速度经过隧道。隧道的入口和出口处均设置有交通执法摄像头。从这两个交通执法摄像头，我们可以很清楚地知道每辆车进入和驶出隧道的顺序。没有两辆车会同时进入隧道，并且也没有两辆车会同时驶出隧道。
交通法规禁止车辆在隧道中超车。如果车辆i在隧道中超了车辆j，那么车辆i的车主就会面临罚款。每辆车的车主最多被罚款一次，即使他在隧道中超车多次。
我们对车辆i超车辆j的定义如下：如果车辆i晚于车辆j进入隧道，并且车辆i早于车辆j驶出隧道，那么车辆i就视为超车了车辆j。
给出车辆按时间顺序进入隧道的顺序和驶出隧道的顺序，编程计算有多少个车主会被罚款。
#include <iostream>
#include <vector>
void get(std::vector<size_t> &a, std::vector<size_t> &b) {
a.clear(); b.clear();
size_t count; std::cin >> count;
for(size_t i = 0; i < count; ++i) {
size_t num; std::cin >> num;
a.push_back(num);
}
for(size_t i = 0; i < count; ++i) {
size_t num; std::cin >> num;
b.push_back(num);
}
}
const std::vector<size_t> verify(const std::vector<size_t> &a, const std::vector<size_t> &b) {
std::vector<size_t> va = a, vb = b, vc;
while(!va.empty()) {
if(va == vb) {
va.erase(va.begin());
vb.erase(vb.begin());
} else {
vc.push_back(vb);
for(auto iter = va.begin(); iter != va.end(); ++iter) {
if(*iter == vb) {va.erase(iter); break;}
}
vb.erase(vb.begin());
}
}
return vc;
}
int main() {
std::vector<size_t> a, b, c;
get(a, b); c = verify(a, b);
for(const auto &num: c) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
页:
[1]