牛客2021年4月15号模拟笔试题

前两天在牛客网做了模拟笔试题，有两道感觉挺有意思的，这里总结一下。其中一道题稍微修改了点条件，进阶一下。

特么的我都不想说，其实这修改的条件是我笔试时没读清题，直接往难了去想的，就没做出来（呜呜呜，哭晕在厕所）。以后做题一定要审清题啊！！！

第1题

牛牛和牛妹最近迷上了新版消消看，该游戏规则如下：

在一个01串中，每一轮，玩家都可以选择一串连续相同字符进行消除，消除之后，左右两侧剩余的字符自动拼接，重新形成一个字符串。

例如，在101001中，牛牛选择了第四个和第五个字符，它们连续且都是0，满足消除条件，而当它们消除之后，左侧剩余的101和右侧剩余的1会拼接到一起，即，消除后剩余的01串为：1011。

计分规则如下：消除了几个1就计几分。允许消除单个字符，因此，直到消成空串时游戏结束。

对于给定的01串，由牛妹先手进行消除，两个人都以最优策略且以得分高为目标进行消除，请问最后，哪个人的得分会比较高？返回一个二元数组，分别是先手得分和后者得分。

进阶：如果不允许只消除单个字符，也就是说，直到消成没有连续的1或0后游戏就结束。

例子1：

输入: s = "0110110101001111"
输出: [7, 3]
解释: 先手得分为 4 + 2 + 1 = 7, 后手得分为 2 + 1 = 3

进阶的例子2：

输入: s = "011011001001001111"
输出: [8, 2]
解释: 先手得分为 4 + 2 + 2 = 8, 后手得分为 2
原始串     --> 011011001001001111
   消    1 --> 000000001001000000 得分：6, 2
后手消   0 --> 1001000000 得分：6, 2
先手消   0 --> 1001 得分：6, 2
后手消   0 --> 11 得分：6, 2
   消    1 --> 00 得分：8, 2

// 对于允许消除单个字符的情况
// 1. 先消除 1, 先手必定选择先消除最长的 1 串
// 2. 后手同样如此, 如此交替下去, 直到串中没有 1
// 3. 此时剩下的全为 0, 消除也不得分
// 因此, 只需要统计串中连续 1 的个数组成数组
// 对数组排序, 偶数索引的值累加为先手的得分
// 奇数索引的值累加为后手的得分
vector<int> eliminate_01_series(const string& series) {
    vector<int> scores(2);
    vector<int> ones = countOnes(series);
    int n = ones.size();
    sort(ones.rbegin(), ones.rend());
    for(int i = 0; i < n; i += 2) {
        scores[0] += ones[i];
    }
    for(int i = 1; i < n; i += 2) {
        scores[1] += ones[i];
    }
    return scores;
}

vector<int> countOnes(const string& series) {
    vector<int> ones;
    int left = 0, right = 0;
    int n = series.size();
    while(right < n) {
        if(series[right] == '1') {
            left = right;
            while(right < n && series[right] != '0') {
                right++;
            }
            ones.push_back(right - left);
        }
        else {
            right++;
        }
    }
    return ones;
}

// (也可能是我想复杂了, 如果你有更简单的方法一定告诉我!)

// 还是有问题，忽略吧

/*
不允许消除单个字符的话，情况就复杂的多了
1. 先按照上题的方案双方先消 1 (消连续 1 的时候有个小技巧, 不实际地把串中连续的 1 擦除,
  而把这些 1 反转为 0 即可), 消完 1 之后再开始消连续的 0
2. 这时候要根据上次消 1 时的 (1 的个数的数组) 的 (连续多个 1) 的个数奇偶性
  来判断谁先消 0 (奇数话就是原先的后手先消 0，偶数的话是原先的先手先消 0)
3. 因为消 0 又不得分. 消一次 0, 在串中实际地擦除 0, 得新串, 对新串递归调用回到第 1 步
4. 擦除 0 的时候还要注意, 对于这样的串 0001000101000 优先从最前面或最后面擦除
  可让对手不得分

下面是调试输出
原始串     --> 00111010011100101001010010010000111011
    消   1 --> 00000010000000101001010010010000000000 得分：6, 5
先手消   0 --> 10000000101001010010010000000000 得分：6, 5
后手消   0 --> 1000000010100101001001 得分：6, 5
先手消   0 --> 110100101001001 得分：6, 5
    消   1 --> 000100101001001 得分：6, 7
先手消   0 --> 100101001001 得分：6, 7
后手消   0 --> 1001010011 得分：6, 7
    消   1 --> 1001010000 得分：8, 7
后手消   0 --> 100101 得分：8, 7
先手消   0 --> 1101 得分：8, 7
    消   1 --> 0001 得分：8, 9
先手消   0 --> 1 得分：8, 9

下面具体看代码注释
*/
vector<int> eliminate_01_series(const string& series) 
    // 得分数组, [先手得分, 后手得分]
    vector<int> scores(2);
    // 调试代码
    cout << "原始串 --> " << series << endl;
    helper(series, scores, 0);
    return scores;
}

// series 为当前串
// flag == 0 表示本次先手先消, flag == 1 表示本次后手先消
void helper(const string& series, vector<int> &scores, int flag) 
    // 首先计算串中 1 的个数数组, 注意返回的是一个 pair 数组
    // pair 中的元素为 {连续 1 的个数, 对应在串中的起始索引}
    vector<pair<int, int>> ones = countContinuousChar(series, '1');
    // 没有 1 就直接返回, 再消也不得分了
    if(ones.empty()) {
        return;
    }
    // 排序, 从大到小
    sort(ones.begin(), ones.end(), greater<pair<int, int>>());
    // 如果有多个连续的 1 进入
    // 没有的话说明这时该消 0 了, 跳过下一步
    if(ones.front().first > 1) {
        int i = 0;
        // 偶数索引元素之和为先手得分
        for (; i < ones.size() && ones[i].first > 1; i += 2) {
            scores[flag] += ones[i].first;
            turnToZeros(series, ones[i].second, ones[i].first);
        }
        int j = 1;
        // 奇数索引元素之和为先手得分
        for (; j < ones.size() && ones[j].first > 1; j += 2) {
            scores[1 - flag] += ones[j].first;
            turnToZeros(series, ones[j].second, ones[j].first);
        }
        // 调试代码
        cout << "    消   1 --> " << series << " 得分：" << scores[0] << ", " << scores[1] << endl;
        // 判断先后手是否转换
        if(i > j) {
            flag = 1 - flag;
        }
        helper(series, scores, flag);
        return;
    }
    // 到这里说明串中没有连续的 1 了
    // 计算 0 串的个数数组
    vector<pair<int, int>> zeros = countContinuousChar(series, '0');
    // 如果为空直接返回
    if(zeros.empty()) {
        return;
    }
    sort(zeros.begin(), zeros.end(), greater<pair<int, int>>());
    // 如果有连续的 0
    if(zeros.front().first > 1) {
        // 优先擦除从 0 索引起始的或最后结尾的 0 串
        // 因为这样可以让下次对手不得分
        // 比如 0001001000 的情况
        if(series[0] == '0' && series[1] == '0') {
            series.erase(0, series.find_first_of('1'));
        }
        else if(series[series.size() - 2] == '0' && series[series.size() - 1] == '0') {
            series.erase(series.find_last_of('1') + 1);
        }
        else {
            // 否则擦除中间任何 0 串都一样
            series.erase(zeros.front().second, zeros.front().first);
        }
        // 调试代码
        if(flag == 0) {
            cout << "先手消   0 --> " << series << " 得分：" << scores[0] << ", " << scores[1] << endl;
        }
        else {
            cout << "后手消   0 --> " << series << " 得分：" << scores[0] << ", " << scores[1] << endl;
        }
        // 注意这里始终要先后手转换
        helper(series, scores, 1 - flag);
    }
    // 如果也没有连续的 0, 那就游戏结束
}

vector<pair<int, int>> countContinuousChar(const string& series, char c) {
    vector<pair<int, int>> ones;
    int left = 0, right = 0;
    while(right < series.size()) {
        if(series[right] == c) {
            left = right;
            while(right < series.size() && series[right] != ('0' + '1' - c)) {
                right++;
            }
            ones.push_back({right - left, left});
        }
        else {
            right++;
        }
    }
    return ones;
}

void turnToZeros(string& series, int pos, int len) {
    for(int i = 0; i < len; i++) {
        series[pos + i] = '0';
    }
}

第2题

西部世界有n个赏金猎人，每个赏金猎人都有两个属性战斗里和所拥有金钱。attack[i]和money[i]分别表示第i个赏金猎人的战斗力和所拥有金钱，保证每个赏金猎人的战斗力不相同。每个赏金猎人都只有k发子弹，这意味着他最多可以击败k个战斗力比他小的赏金猎人并获取他们的金钱。输出每一个赏金猎人最多拥有多少金钱。

Constraints:

• 1 <= n <= 10^5^, 0 <= k <= min(n - 1, 10).

• 1 <= attack[i], money[i] <= 10^9^.

vector<int> maxMoney(vector<int> &attack, vector<int> &money, int k) {
    // 记录每个赏金猎人的战斗里和他所对应的索引
    // 并利用其自动排序的特性
    // 对赏金猎人的战斗力进行排序
    // 这样在遍历的时候就能保证之前遍历的都是比他战斗力小的
    map<int, int> mapping;
    for(int i = 0; i < attack.size(); i++) {
        mapping[attack[i]] = i;
    }
    // 返回金钱数组里初始化为自身拥有的本金
    vector<int> res(money);
    // 维护一个最小堆, 堆固定大小为 k
    // 最多存储 k 个比当前赏金猎人的战斗力小的赏金猎人
    vector<int> heap;
    for(auto& p : mapping) {
        // 如果堆不为空的话, 堆里的金钱数就是当前赏金猎人增加的金钱数
        // 因为排序后遍历的原因, 堆里的猎人的战斗力都比他小
        if(!heap.empty()) {
            res[p.second] += accumulate(heap.begin(), heap.end(), 0);
        }
        // 定制成最小堆
        heap.push_back(money[p.second]);
        push_heap(heap.begin(), heap.end(), greater<int>());
        if(heap.size() > k) {
            pop_heap(heap.begin(), heap.end(), greater<int>());
            heap.pop_back();
        }
    }
    return res;
}

// 使用用优先级队列做为堆
// 使用一个整数变量 sum 时刻保持为堆内元素总和
// 这样代码更简单, 还不用每次求堆内元素和
vector<int> maxMoney(vector<int> &attack, vector<int> &money, int k) {
    // 记录每个赏金猎人的战斗里和他所对应的索引
    // 并利用其自动排序的特性
    // 对赏金猎人的战斗力进行排序
    // 这样在遍历的时候就能保证之前遍历的都是比他战斗力小的
    map<int, int> mapping;
    for(int i = 0; i < attack.size(); i++) {
        mapping[attack[i]] = i;
    }
    // 返回金钱数组里初始化为自身拥有的本金
    vector<int> res(money);
    // 维护一个最小堆, 堆固定大小为 k
    // 最多存储 k 个比当前赏金猎人的战斗力小的赏金猎人
    priority_queue<int, vector<int>, greater<int>> heap;
    int sum = 0; // 堆内元素总和
    for(auto &p : mapping) {
        // 如果堆不为空的话, 堆里的金钱数就是当前赏金猎人增加的金钱数
        // 因为排序后遍历的原因, 堆里的猎人的战斗力都比他小
        if(!heap.empty()) {
            res[p.second] += sum;
        }
        // 定制成最小堆
        sum += money[p.second];
        heap.push(money[p.second]);
        if(heap.size() > k) {
            sum -= heap.top();
            heap.pop();
        }
    }
    return res;
}