小红的纸牌游戏

[题目链接](https://www.nowcoder.com/practice/a454e716209c467c924577295f6e0d8d)

思路

本题是一个博弈 + 贪心问题。 $n$ 张纸牌排成一行，每张上面写着 $0$ 或 $1$ 。小红和小紫轮流取走一张牌（小红先手），直到剩下 $k$ 张牌，剩余牌按原始顺序拼成一个二进制数。小红想让这个数尽可能大，小紫想让它尽可能小。

贪心策略

二进制数的高位比低位重要得多，因此双方都应该优先影响高位。对于每一方：

小红（最大化）：希望高位是 $1$ ，因此她应该移除最左边的 $0$ 。去掉一个靠前的 $0$ ，相当于让后面的 $1$ 顶上更高位。如果没有 $0$ 可移除（全是 $1$ ），那移除哪张都一样，选择移除最右边的 $1$ 以保留尽可能多的高位。

小紫（最小化）：希望高位是 $0$ ，因此她应该移除最左边的 $1$ 。去掉一个靠前的 $1$ ，相当于让后面的 $0$ 顶上更高位。如果没有 $1$ 可移除（全是 $0$ ），选择移除最右边的 $0$ 。

举例

以样例 10110， $n=5$ ， $k=3$ 为例，共需移除 $2$ 张牌：

轮次	玩家	操作	剩余牌
初始	—	—	`10110`
1	小红	移除最左边的 0（第 2 张）	`1110`
2	小紫	移除最左边的 1（第 1 张）	`110`

最终结果为 110。

正确性

这个贪心策略之所以正确，是因为在二进制表示中，高位的权重远大于所有低位权重之和（ $2^i > \sum_{j=0}^{i-1} 2^j$ ）。因此无论后续局面如何变化，优先操作最左边（最高位方向）的目标字符，都能带来最大收益。

代码

直接模拟博弈过程。用链表维护当前牌序列，每轮按贪心策略移除对应字符。

C++
Java

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    char s[200005];
    scanf("%s", s);

    list<char> cards(s, s + n);

    int removals = n - k;
    for (int turn = 0; turn < removals; turn++) {
        if (turn % 2 == 0) {
            // 小红：移除最左边的 '0'，若无则移除最右边的 '1'
            auto it = find(cards.begin(), cards.end(), '0');
            if (it != cards.end()) {
                cards.erase(it);
            } else {
                auto rit = cards.end();
                --rit;
                cards.erase(rit);
            }
        } else {
            // 小紫：移除最左边的 '1'，若无则移除最右边的 '0'
            auto it = find(cards.begin(), cards.end(), '1');
            if (it != cards.end()) {
                cards.erase(it);
            } else {
                auto rit = cards.end();
                --rit;
                cards.erase(rit);
            }
        }
    }

    for (char c : cards) putchar(c);
    putchar('\n');
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), k = sc.nextInt();
        String s = sc.next();

        LinkedList<Character> cards = new LinkedList<>();
        for (char c : s.toCharArray()) cards.add(c);

        int removals = n - k;
        for (int turn = 0; turn < removals; turn++) {
            if (turn % 2 == 0) {
                // 小红：移除最左边的 '0'，若无则移除最右边的 '1'
                int idx = cards.indexOf('0');
                if (idx != -1) {
                    cards.remove(idx);
                } else {
                    cards.removeLast();
                }
            } else {
                // 小紫：移除最左边的 '1'，若无则移除最右边的 '0'
                int idx = cards.indexOf('1');
                if (idx != -1) {
                    cards.remove(idx);
                } else {
                    cards.removeLast();
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (char c : cards) sb.append(c);
        System.out.println(sb.toString());
    }
}

复杂度分析

时间复杂度： $O(n^2)$ ，共 $n - k$ 轮，每轮在链表中查找目标字符需要 $O(n)$ 。对于本题 $n \le 2 \times 10^5$ 的数据范围，可以通过。
空间复杂度： $O(n)$ ，链表存储所有牌。