微众银行笔试 微众银行软件算法笔试

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

1、区间计数

题目描述：

给出两个长度均为n的数组A={a1,a2,...,an}，B={b1,b2,...,bn}。你需要求出其有多少个区间[L,R]满足数组A中下标在[L,R]中的元素之和在[La,Ra]之中，且数组B中下标在[L,R]中的元素之和在[Lb,Rb]中。

输入描述

第一行有一个正整数N(1≤N≤100000)，代表两个数组的长度。

第二行有N个非负整数，范围在0到1000000000之间，代表数组中的元素。

第三行有N个非负整数，范围在0到1000000000之间，代表数组中的元素。

第四行有4个整数La,Ra,Lb,Rb，范围在0到1018之间，代表题目描述中的参数。

输出描述

输出一个整数，代表所求的答案。

样例输入

4

1 4 2 3

2 4 1 1

3 7 4 6

样例输出

3

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>

using namespace std;

int bcs1(const vector<int>& nums, int l, int r, int target) {
    while (l < r) {
        int mid = (l + r) / 2;
        if (nums[mid] >= target) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return r;
}

int bcs2(const vector<int>& nums, int l, int r, int target) {
    while (l < r) {
        int mid = (l + r + 1) / 2;
        if (nums[mid] <= target) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }
    return r;
}

int main() {
    int N;
    cin >> N;

    vector<int> A(N), B(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }
    for (int i = 0; i < N; ++i) {
        cin >> B[i];
    }

    int La, Ra, Lb, Rb;
    cin >> La >> Ra >> Lb >> Rb;

    vector<int> preA(N + 1), preB(N + 1);

    for (int i = 1; i <= N; ++i) {
        preA[i] = preA[i - 1] + A[i - 1];
        preB[i] = preB[i - 1] + B[i - 1];
    }

    int cnt = 0;

    for (int i = 0; i <= N; ++i) {
        int l = 0, r = i;
        int l1 = bcs1(preA, l, r, preA[i] - Ra);
        int r1 = bcs2(preA, l, r, preA[i] - La);
        int l2 = bcs1(preB, l, r, preB[i] - Rb);
        int r2 = bcs2(preB, l, r, preB[i] - Lb);
        int l3 = max(l1, l2);
        int r3 = min(r1, r2);
        
        if (La <= preA[i] - preA[l3] && preA[i] - preA[l3] <= Ra &&
            La <= preA[i] - preA[r3] && preA[i] - preA[r3] <= Ra &&
            Lb <= preB[i] - preB[l3] && preB[i] - preB[l3] <= Rb &&
            Lb <= preB[i] - preB[r3] && preB[i] - preB[r3] <= Rb) {
            cnt += r3 - l3 + 1;
        }
    }

    cout << cnt << endl;

    return 0;
}

2、吞吞大作战

题目描述：

吞吞大作战是球球大作战的x.0版本，此时球球并不能通过击败其他球球壮大自己，而是获得得分，每一个球球都有一个能量值a_i，能量大的球球可以击败能量小的球球，当一个球球被击败后，击败者可以获得b_i得分。但是为了和谐，每个球球最多只能击败m个其他球球，然后就会强制进入结算环节。数据保证不会有两个球球具有相同的能量值。  请问每个球球最终最多得分多少。

输入描述

输入第一行包含