[已解决]超车问题

取个jer名字

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

最佳答案

月排行榜 / 总排行榜

人造人

2021-3-12 23:09:10

#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[0] == vb[0]) {
            va.erase(va.begin());
            vb.erase(vb.begin());
        } else {
            vc.push_back(vb[0]);
            for(auto iter = va.begin(); iter != va.end(); ++iter) {
                if(*iter == vb[0]) {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;
}

跳转到最佳答案楼层

人造人

#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[0] == vb[0]) {
            va.erase(va.begin());
            vb.erase(vb.begin());
        } else {
            vc.push_back(vb[0]);
            for(auto iter = va.begin(); iter != va.end(); ++iter) {
                if(*iter == vb[0]) {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;
}