拼多多0312笔试总结

写在前面：

拼多多的暑期实习招聘题目相对来说难度不大，题面也比较好理解，本篇文章仅分享本人解答代码做学习交流，若涉密或侵权可联系我删除。

题目 1

题目描述

大致意思是给你一个压缩的字符串，让你还原出原始字符串，属于一个简单的模拟题目，样例如下：

10a1b1c -> aaaaaaaaaabc
1P2D1p2d1P1D1d -> PDDpddPDd

解题方法

直接模拟，字符串处理。

#include<bits/stdc++.h>

using namespace std;

int main() {
    string s;
    cin>>s;
    int i = 0;
    while (i < s.length()) {
        int num = 0;
        while (isdigit(s[i])) {
            num = num*10 + s[i++]-'0';
        }
        for (int k = 0; k < num; k++) {
            cout << s[i];
        }
        i++;
    }
    return 0;
}

题目 2

题目描述

T 个关卡，每个关卡 N 个敌人。需要打败所有敌人，现在有两种操作：

A 攻击：命中两个敌人，每个耐受值 -1。

B 攻击：命中一个敌人，直接消灭。

求打败所有敌人所需要操作的最小次数。

解题方法

贪心。对于一个敌人如果其耐受值 >= 2，可以直接使用 B 攻击；可以使用 A 攻击同时击杀两个耐受值为 1 的敌人。因此只需要统计两种敌人的数量即可。

#include<bits/stdc++.h>

using namespace std;

int main() {
    int t, n;
    cin>>t>>n;
    for (int i = 0; i < t; i++) {
        int more = 0, one = 0, cnt = 0;
        for (int j = 0; j < n; j++) {
            int tmp;
            cin>>tmp;
            if (tmp >= 2) {
                more++;
            }
            else {
                one++;
            }
        }
        cout << (more + (one + 1)/2) << endl;
    }
}

题目 3

题目描述

第一行，一个整数 N ，代表准备参加活动的人数。\((1 \le N \le 100)\)

接下来 N 行，每行一个由 "ABC" 组成的字符串，其中第 i 行表示第 i 个人投票了哪几个活动。（输入保证字符串非空，且由大写的 "ABC" 字符组成）

最后 3 行，每行两个整数，分别表示三个活动的人数上限以及每个人参加的费用。（人数上限以及参与活动的费用均为不超过 100 的正整数）

样例

输入

5
A
B
C
AB
ABC
2 1
2 2
2 3

输出

YES
9

解题方法

动态规划。这道题其实在笔试的时候没有想到 DP ，而是直接使用贪心来做，没想到竟然骗了 95% 的分，题目数据可能比较弱，看到牛客上也有用贪心过了 100% 的。

赛中贪心解法(95%)：

#include<bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin>>n;
    vector<pair<int, int>> activaty(3);
    vector<vector<int>> want(n);
    for (int i = 0; i < n; i++) {
        string s = "";
        cin >> s;
        for (auto &ch : s) {
            want[i].push_back(ch - 'A');
        }
    }
    for (int i = 0; i < 3; i++) {
        cin >> activaty[i].first >> activaty[i].second;
    }
    for (int i = 0; i < n; i++) {
        sort(want[i].begin(), want[i].end(), [&](auto &a, auto &b) {
            return activaty[a].second < activaty[b].second;
        });
    }
    sort(want.begin(), want.end(), [](auto &a, auto &b) {
        return a.size() == b.size() ? a < b:a.size() < b.size();
    });
    int ans = 0;
    vector<int> isok;
    for (int i = 0; i < n; i++) {
        for (auto &w : want[i]) {
            if (activaty[w].first <= 0) {
                continue;
            }
            else {
                ans += activaty[w].second;
                activaty[w].first--;
                isok.push_back(i);
                break;
            }
        }
    }
    if (isok.size() == n) {
        cout << "YES\n" << ans << endl;
    }
    else {
        cout << "NO\n" << isok.size() << endl;
    }
}

赛后看到一种 dp 思路，\(dp[i][j][k]\) 表示前 \(i\) 个人，\(j\) 个选 A，\(k\) 个选 B，\(i-j-k\) 个人选 C，的最小值，后续有时间写一下。

// todo

题目 3

题目描述

大致意思就是给你一个数组，长度为 n，让你输出两个长度为 n 的序列 \(A\)，\(A_i\) 分别代表前 i 个数的中位数和平均数。

解题方法

数据流的中位数，借助两个栈即可实现，Leetcode 原题：剑指 Offer 41. 数据流中的中位数

#include<bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin>>n;
    long long int _sum = 0;
    priority_queue<int, vector<int>, less<int>> small;
    priority_queue<int, vector<int>, greater<int>> big;
    vector<long long> ans1, ans2;
    for (int i = 0; i < n; i++) {
        long long num;
        cin>>num;
        _sum += num;
        if (small.empty() || num <= small.top()) {
            small.push(num);
            if (big.size() + 1 < small.size()) {
                big.push(small.top());
                small.pop();
            }
        }
        else {
            big.push(num);
            if (big.size() > small.size()) {
                small.push(big.top());
                big.pop();
            }
        }
        long long average = (long long)(1.0*_sum/(i+1) + 0.5);
        int middle = 0;
        if (small.size() != big.size()) {
            middle = small.top();
        }
        else {
            middle = (small.top() + big.top() + 1)/2;
        }
        ans1.emplace_back(average);
        ans2.emplace_back(middle);
    }
    for (int i = 0; i < n; i++) {
        cout<<ans1[i]<<" ";
    }
    cout<<endl;
    for (int j = 0; j < n; j++) {
        cout<<ans2[j]<<" ";
    }
    cout<<endl;
}