「技术笔试」拼多多 2023-03-12

自我感觉难度要比 2021 年的高一档。但每个人的感受不同，因人而异吧。下面简单回顾一下题意和解法。

A

简要题意

还原压缩后的字符串，例如 10a1b1c -> aaaaaaaaaabc，1P2D1p2d1P1D1d -> PDDpddPDd。

思路

模拟题，遇到数据累计一下，遇到字母则追加到答案中。

代码

string solve(string s) {
    int cnt = 0;
    string t;
    for (int i = 0; i < s.size(); i++) {
        if (isdigit(s[i])) {
            cnt = cnt * 10 + s[i] - '0';
        } else {
            while (cnt--) {
                t += s[i];
            }
        }
    }
    return t;
}

B

简要题意

T 个关卡，每个关卡 n 个敌人，每个敌人的耐受值已知。每一关是独立的，你需要打败所有敌人，现在有两种操作：

1. 选择两个敌人，每个耐受值 -1。
2. 选择一个敌人，直接消灭。

求打败当前关卡所有敌人所需要操作的最小次数。（当前关卡的操作不会影响到之后的关卡）

思路

操作 2 应该尽可能的去消灭耐受力大的敌人，因此先对敌人排序（从小到大），然后考虑枚举操作 2 的次数，再去求操作 1 的执行次数。

求解操作 1 的次数思路有点像 ***************************************************************** 。具体操作请看代码~

void solve() {
    int pre = 0; // [0, i - 1] 的和
    for (int i = 0; i < n; i++) {
        int B = n - i - 1; // 操作 2 的次数
        int A = 0;
        if (pre < d[i]) {
            // 如果 [0, i - 1] 的和 pre 小于 d[i], 则配对 pre 次之后仍然需要一次 2 操作
            A = pre + 1;
            pre += d[i];
        } else {
        	pre += d[i];
            // 否则，我们总是可以找两个当前耐力值最大的去减，如果总和是奇数，那么仍然需要一次 2 操作
            A = (pre / 2) + (pre & 1);
        }
        res = min(res, A + B);
    }
}

更简单的，当耐受度大于 1 时，必然是用操作 2 更划算，因此直接计算（n - sum(d[i] == 1) / 2) 即可。

C

简要题意

3 种活动，n 个员工每人可以选想去参加的活动志愿，但最终只能去一个。每个活动有人数限制以及单位价格。问能否安排所有的人去参加活动，如果可以，求出最少花费，如果不行，输出最多可以安排多少人去参加。(n <= 100)。

思路

我先想了一种贪心的方法，但没有通过，不太清楚错哪里了。大概想法如下：

1. 先强制安排只有一种志愿的。
2. 然后对于三个志愿的，放在最后安排。（如果还有剩余，则优先选价格低的）
3. 对于选择两个志愿的，分别是 AB，BC，CD，枚举它们的选择

a. AB 中有 x1 人选了 A，x2 人选了 B

b. BC 中有 y1 人选了 B，x2 人选了 C

c. AC 中有 z1 人选了 A，z2 人选了 C

我们枚举了 6 个值，平摊下来最多的复杂度应该差不多是 (100 / 6)^6，勉强不超时。但是不明白这个答案是不是有问题。

正确而简单的思路是「最小费用流」。源点向每个人连流量 1，费用 0 的边，每个人向志愿连流量 1 费用 0 的边，每个志愿向汇点连流量为人数限制，费用为单位价格的边，然后直接跑模板即可~

动态规划方法一

动态规划，状态为 表示前 i 个人选了 j 个 A，k 个 B，l 个 C 的最小花费。时间复杂度为 O(n^4) 也可以通过。空间的话可以用滚动数组压缩，或者用 bool 数组四维判是否为 NO，再用三维求最小花费。

动态规划方法二

问了某群群友，提供了如下思路：

表示前 i 个人，选了 j 个 A，k 个 B 之后，最多可以选择多少个 C。O(n^3) 的时间复杂度和空间复杂度（滚动可以降一维）。可以求出是否存在合法方案，以及所有合法情况中的最小花费。不得不说，这一手状态设计的妙啊~

代码附上（只测了样例数据）

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int main() {
    int n;
    cin >> n;
    vector<string> fac(n + 1);
    vector<int> limit(3), cost(3);
    for (int i = 1; i <= n; i++) {
        cin >> fac[i];
    }
    for (int i = 0; i < 3; i++) {
        cin >> limit[i] >> cost[i];
    }
    vector d(n + 1, vector(limit[0] + 1, vector<int>(limit[1] + 1, -1)));
    d[0][0][0] = 0;
    auto checkIn = [&](string &fac, char ch) { return fac.find(ch) != -1; };

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= limit[0]; j++) {
            for (int k = 0; k <= limit[1]; k++) {
                d[i][j][k] = max(d[i][j][k], d[i - 1][j][k]);
                if (j > 0 && checkIn(fac[i], 'A')) {
                    d[i][j][k] = max(d[i][j][k], d[i - 1][j - 1][k]);
                }
                if (k > 0 && checkIn(fac[i], 'B')) {
                    d[i][j][k] = max(d[i][j][k], d[i - 1][j][k - 1]);
                }
                if (checkIn(fac[i], 'C')) {
                    d[i][j][k] = max(d[i][j][k], min(d[i - 1][j][k] + 1, limit[2]));
                }
            }
        }
    }

    int max_cnt = 0, min_cost = INF;
    for (int j = 0; j <= limit[0]; j++) {
        for (int k = 0; k <= limit[1]; k++) {
            if (d[n][j][k] == -1) continue;
            int cnt = j + k + d[n][j][k];
            int cost_sum = cost[0] * j + cost[1] * k + cost[2] * d[n][j][k];
            if (cnt > max_cnt) {
                max_cnt = cnt;
                min_cost = cost_sum;
            } else if (cnt == max_cnt) {
                min_cost = min(min_cost, cost_sum);
            }
        }
    }
    if (max_cnt != n) {
        cout << "NO\n" << max_cnt << "\n";
    } else {
        cout << "YES\n" << min_cost << "\n";
    }
    return 0;
}

D

简要题意

维护数据流的平均数和中位数。

思路

平均数很好维护，但要注意数据范围，并且这个题目出题人有些小心思（可能是这样吧hhh），卡了精度。直接转 double 是过不了的。

for (int i = 0; i < n; i++) {
    // mean 为平均值，extra 为余数
    int mean = sum / (i + 1);
    int extra = sum % (i + 1);
    if (extra * 2 >= (i + 1)) {
        mean++;
    }
}

对于中位数，使用堆顶对维护即可，注意四舍五入。是比较套路的问题，可以参考：***********************************************************