微众银行软件算法笔试

校招一对一进阶提高，带领学员斩获大厂实习秋招春招offer！！！

****************

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个其他球球，然后就会强制进入结算环节。数据保证不会有两个球球具有相同的能量值。  请问每个球球最终最多得分多少。

输入描述

输入第一行包含两个正整数n和m，表示球球的数量，和每个球球最多击败其他球球的数量。(1<=n,m<=1e5)

输入第二行包含n个非负整数，表示每个球球的能量值，每个数都不大于100000。

输入第三行包含n个正整数，表示每个球球的被击败后对手获得的得分，每个整数都不大于100000。

输出描述

输出包含n个整数，表示每个球球最终最多获得的分数。

样例输入

5 3

1 3 5 2 4

1 2 3 4 5

样例输出

0 5 11 1 7

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <functional>

using namespace std;

struct Ball {
    int power;
    int score;
    int index;
};

int main() {
    int n, m;
    cin >> n >> m;

    vector<int> pwrs(n), scores(n);
    for (int i = 0; i < n; ++i) {
        cin >> pwrs[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> scores[i];
    }

    vector<Ball> balls(n);

    for (int i = 0; i < n; ++i) {
        balls[i].power = pwrs[i];
        balls[i].score = scores[i];
        balls[i].index = i;
    }

    sort(balls.begin(), balls.end(), [](const Ball& a, const Ball& b) {
        return a.power < b.power;
    });

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> heap;
    heap.push({balls[0].score, balls[0].index});

    int cur = balls[0].score;
    vector<int> res(n);

    for (int i = 1; i < n; ++i) {
        int pwr = balls[i].score;
        int index = balls[i].index;
        res[index] = cur;
        
        if (heap.size() < m) {
            heap.push({pwr, index});
            cur += pwr;
        } else {
            if (pwr > heap.top().first) {
                cur -= heap.top().first;
                heap.pop();
                heap.push({pwr, index});
                cur += pwr;
            }
        }
    }

    for (int r : res) {
        cout << r << " ";
    }
    cout << endl;

    return 0;
}

3、混乱的键盘

题目描述：

小可每天都要将很多文件输入到电脑里面去，由于键盘长期的使用，导致键盘出现了一些bug,如果你连续敲击了某个键k次后，再次敲击该键位的话，却不会有任何的输入，这个bug可以通过两种方式解决，一种是在这个时候敲击另一个键位，或者是再敲击k次这个键位，从而使得这个bug 被修复。

现在小可又收到了一份文件，文件里面有着一堆这样的连续的需要被键入的文字，但是由于小可使用的键盘是特制的字符集巨大的键盘，所以她不能使用删除键来进行操作，所以小可想知道，如果她需要输入接下来这个文件，那么她需要以怎样的方式来敲击键盘？但如果你把小可需要输出的字符丢在她面前，那也过于冗长了，因此小可只想知道对于每个键小可需要敲击多少次。

输入描述

输入数据共n+1行

第一行输入2个整数 n,k，表示文件的连续段数目和产生 bug 的临界值。

接下来行每行2个正整数ai,bi，表示ai这个字符将会紧接着输入bi次。

对于所有的数据，1≤n,k≤10^5,ai≤10^9,bi≤10^9

输出描述

输出共m+1行（m为字符的种类数）

第一行 输出一个整数m，表示小可需要敲击的键位数。

接下来m行每行两个正整数ci,di,表示ci这个字符键被敲击了di次。注意此处需要按照ci大小从小往大的顺序输出。

样例输入

6 4

1 3

1 3

2 1

1 9

2 2

2 10

样例输出

2

1 27

2 21

样例解释

首先一共需要用到1,2两种键，在1号键键入6次时，实际按了10次，键入9次时，实际按了17次，因此需要敲击1号键27次，同理可以得到2号键的敲击次数。

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

int get_times(int num, int k) {
    if (num % k == 0) {
        return (num / k - 1) * k + num;
    }
    return (num / k) * k + num;
}

int main() {
    int n, k;
    cin >> n >> k;

    vector<pair<int, int>> ins;

    for (int i = 0; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        if (!ins.empty()) {
            if (a == ins.back().first) ins.back().second += b;
            else {
                ins.emplace_back(a, b);
            }
        } else {
            ins.emplace_back(a, b);
        }
    }

    unordered_map<int, int> dic;

    for (const auto &p : ins) {
        int ai = p.first;
        int bi = p.second;
        if (dic.find(ai) == dic.end()) dic[ai] = 0;
        dic[ai] += get_times(bi, k);
    }

    vector<pair<int, int>> res(dic.begin(), dic.end());

    cout << res.size() << endl;
    sort(res.begin(), res.end());

    for (const auto &p : res) {
        int ci = p.first;
        int di = p.second;
        cout << ci << " " << di << endl;
    }

    return 0;
}