招商银行笔试 招商银行软件算法笔试4-28

订阅专栏，方便查阅，时刻更新各厂软件算法笔试https://blog.nowcoder.net/zhuanlan/0oDWVm

题目1：设备故障

小招有一个平常做实验用的集群，偶然发现由于自己维护不当，集群各个设备的时间同步出了问题，导致部分设备的时间不准确。解决了时间同步问题后，他需要评估这次故煌对历史数据造成的影响范围。他想到网关每隔一段时间会同时给所有设备发送健康检查请求，并且各类设备的日志会记录这些请求。于是他导出了某时间段内故集群设备、网络设备和上下游系统的日志，通过分析程房对这些日志数据进行了综合分析。最终，程序输出了N条数据(1<N<1000)每条数据唯一对应一台设备，并且通过分析给出了这台设备关于这同一批请求的推断。第(1  )条数以"L ti”表示这台设备在某本地时间比之前(或给好在比这一时刻收到到该批次健康检查，或是以"G ti”表示这合设备在革本地时间之后(或合好在这-时刻)收到到该批次健康检查，所有比均为标准么处理后的正整数。请各位同学参考分析程序给出的推断帮助他判断，忽略分析程序的误差，在接收到这条请求时，最少有多少台设备的时间是错误的。

输入描述

输入的第一行包括N，接下来的N行每行会包含一个L或G，紧接着是数ti<= 10^9，L代表第条数据猫述T小于等于ti，G代表第条数猫述T大于等于ti。

输出描述

根据分析程序的输出数据，输出最少有多少台设备的时间是错误的。

示例1输入

2

G 1

L 4

输出:

0

示例2输入:

2

G 6

L 5

输出:

1

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

const int MAX = 1e9;

int main() {
    int N;
    std::cin >> N;
    
    std::vector<int> points, XS, YS, LXS, LYS;
    std::map<int, int> point_map;
    
    for (int i = 0; i < N; ++i) {
        char type;
        int point;
        std::cin >> type >> point;
        
        if (type == 'G') {
            XS.push_back(point);
            YS.push_back(MAX);
            points.push_back(point);
            points.push_back(MAX);
        } else {
            XS.push_back(0);
            YS.push_back(point);
            points.push_back(point);
            points.push_back(0);
        }
    }
    
    std::sort(points.begin(), points.end());
    points.erase(unique(points.begin(), points.end()), points.end());
    
    for (int i = 0; i < points.size(); ++i) {
        point_map[points[i]] = i;
    }

    for (int i = 0; i < N; ++i) {
        LXS.push_back(point_map[XS[i]]);
        LYS.push_back(point_map[YS[i]]);
    }

    int size = points.size();
    std::vector<int> diff(size, 0);
    
    auto update = [&](int l, int r, int v) {
        diff[l] += v;
        if (r + 1 < N) {
            diff[r + 1] -= v;
        }
    };

    for (int i = 0; i < N; ++i) {
        int x = LXS[i], y = LYS[i];
        update(x, y, 1);
    }

    std::vector<int> res(N, 0);
    res[0] = diff[0];
    for (int i = 1; i < N; ++i) {
        res[i] = res[i - 1] + diff[i];
    }
    
    std::cout << N - *std::max_element(res.begin(), res.end()) << std::endl;

    return 0;
}

题目2：设备下线

机房里又有一些设备要下线关机，由于配置不同，这些设备处理业务的能力也不同，对于N台设备(1<=N<=1.5x10) ，处理业务的能力分别是ai...aN，也就是说，第i台机器每分钟能够处理的业务量(吞叶量)为ai个单位，其中0<=a<=10%，流量分发策略保证这部分设备始终满负荷运行。工程师需要技照一定顺序依次下线这些设备，并且下线操作均需要持续一分钟时间，如果按照x,y,z的顺序下线设备，那么从工程师正式开始绿作开始，到这三台设备都下线，这三台设备处理的业务量分别是ax、2ay和3az,个单位。

不线提作期间，这部分设备处理的业务量最小值是T，T是如何随着各个设备的否量变化而变化的呢？我们假设通过一些指令来改变一些设备的香叶量，对于0个指令(1<=Q<=1.5x10^5)，每个指令由整数和构成，指令将会使第(1<=i<=N) 台设备的吞量临时变为(j>=0)，请计算在该指令的影响下，T会变为多少? 另外，指令的影响可以看成临时且独立的，也就是说当前指令生效前，之前指令的影响均会被重置。

输入描述

第一行包含整NNa1...an. QQii.