辩论俱乐部（politics.cpp） - 最大成员数量算法优化 - 常规

辩论俱乐部（politics.cpp） - 最大成员数量算法优化

问题描述： 在一个包含你（成员 1）和 n 个成员的辩论俱乐部中，有 k 个议题需要按顺序讨论。在每次讨论中，成员会表达他们同意或不同意的观点。我们将 Y 定义为同意的成员数量，N 为不同意的成员数量。每次讨论后，会员根据以下标准离开俱乐部：

如果同意的成员多于不同意的成员 (Y > N)，则所有不同意的成员都会离开俱乐部。
如果不同意的成员多于同意的成员 (Y < N)，则所有同意的成员都会离开俱乐部。
如果平局 (Y = N)，则所有会员均离开俱乐部。

作为俱乐部主席，你的目标是留在俱乐部并最大程度地使得会议后剩余的成员数量更多。在会议开始之前，你可以了解每个成员对所有 k 个议题的立场，并且你可以在所有会议开始之前就驱逐任意数量的成员（不包括你自己）。

输入格式： 第一行包含两个正整数 n 和 k，分别表示成员数量和讨论数量。接下来 n 行中，第 i 行包含一个长度为 k 的字符串 ti。字符串 ti 中的第 j 个字符表示第 i 个成员同意或不同意第 j 个意见（如果他们没有在会议开始之前就离开俱乐部的话），'+' 号表示同意，'-' 号表示不同意。

输出格式： 一行一个整数，表示所有会议结束后，包括你自己在内可以留在俱乐部的最大会员人数。

输入样例 1：

2 2
++
+-

输出样例 1：

输入样例 2：

1 3
+-+

输出样例 2：

输入样例 3：

4 1
+
-
-
+

输出样例 3：

输入样例 4：

5 4
++++
+--+
++-+
+-++
++++

输出样例 4：

输入样例 5：

4 2
++
--
--
-+

输出样例 5：

样例解释： 对于样例 1，只有第一位成员可以参加会议，否则在讨论第二个议题后，两位成员都会离开。对于样例 2，只有一名成员出席会议并坚持到最后。对于样例 3，俱乐部有 4 名成员，会议期间只会讨论一项议题。让我们根据会议参与者来分析可能的结果：

如果只有第一位成员出席，那么他将是会议结束后剩下的唯一成员。
如果第一个成员与第二个或第三个成员一起参加，他们将在议题中打成平局，导致他们都离开。
如果第一名成员与第二名和第三名成员一起出席，则第一名成员将成为少数派，并在讨论后离开，这与声明相矛盾。
如果第一名和第四名成员出席，他们将在讨论过程中达成一致，并保留到最后。
如果第一、第二、第四名成员参加，则讨论时第二名成员将成为少数，最后只剩下第一、第四名成员。如果第二个成员被第三个成员替换，也会发生同样的情况。
如果四位成员都参加，讨论过程中就会出现平局，导致所有人离开。会议结束后剩余成员最多为 2 人。对于样例 4，俱乐部现有会员 5 名，会议将讨论 4 项议题。实现最大成员人数的一种方法是只有第一、第三和第五名成员参加会议。在这种情况下，他们在前两次讨论中都同意，之后在第三次讨论中第三个成员处于少数。然后，第一名和第五名成员在最后一次讨论中达成一致，这两名成员留到会议结束。对于样例 5，俱乐部有 4 名成员，将讨论 2 条议题。如果前三名成员出席会议，则第一位成员将在第一次讨论中成为少数派，并将离开俱乐部。之后，第二名和第三名成员均不同意第二个意见，并留至会议结束。这样，会议结束后就会剩下 2 名成员，但这是一个无效的结果，因为它迫使第一个成员离开。因此，只能只有第一位成员出席会议，此时，达到 1 名成员的最大人数。

数据范围及约定： 对于 100% 的数据，1 ≤ n, k ≤ 100

思路： 根据题目描述，我们需要找到一种方法，使得会议结束后剩余的成员数量最多。首先，我们需要确定在每一次讨论后，哪些成员会离开俱乐部。根据题目描述，如果同意的成员多于不同意的成员 (Y > N)，则所有不同意的成员都会离开俱乐部；如果不同意的成员多于同意的成员 (Y < N)，则所有同意的成员都会离开俱乐部；如果平局 (Y = N)，则所有会员均离开俱乐部。根据上述规则，我们可以得出以下结论：

如果在某次讨论中，同意的成员数量大于不同意的成员数量，我们应该让不同意的成员离开，因为这样可以最大程度地保留同意的成员。
如果在某次讨论中，不同意的成员数量大于同意的成员数量，我们应该让同意的成员离开，因为这样可以最大程度地保留不同意的成员。
如果在某次讨论中，同意的成员数量等于不同意的成员数量，我们应该让所有成员离开，因为无论选择哪一方，都会导致平局。基于上述结论，我们可以采取贪心策略来选择每一次讨论中留下的成员。

具体实现如下：

初始化当前剩余成员数量为 n。
对每一次讨论进行循环： a. 统计同意和不同意的成员数量。 b. 如果同意的成员数量大于不同意的成员数量，将不同意的成员数量更新为 0，剩余成员数量更新为同意的成员数量。 c. 如果不同意的成员数量大于同意的成员数量，将同意的成员数量更新为 0，剩余成员数量更新为不同意的成员数量。 d. 如果同意的成员数量等于不同意的成员数量，将剩余成员数量更新为 0。
输出剩余成员数量。

时间复杂度分析： 假设 n 为成员数量，k 为讨论数量，则统计每一次讨论的时间复杂度为 O(k)。总共有 k 次讨论，因此总时间复杂度为 O(k^2)。由于 k ≤ 100，所以该算法的时间复杂度是可以接受的。