议题（politics.cpp） - 辩论俱乐部成员保留问题 - C++ 实现 - 常规

议题（politics.cpp） - 辩论俱乐部成员保留问题 - C++ 实现

时间限制：1s 空间限制：512 MB

问题描述

在一个包括你自己（成员 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

思路：

根据题意，会议结束时剩下的成员最多为1人或2人。假设剩下的成员数量为x，那么在每一次讨论中，至少有x个成员同意，否则会议结束后剩下的成员数量就会少于x。因此，我们可以遍历所有可能的剩下成员数量x（x=1或2），对于每个x，遍历所有讨论，统计同意和不同意的成员数量，根据条件判断剩下的成员数量是否与x一致，如果一致则记录下来，最后输出满足条件的最大剩下成员数量。

具体步骤如下：

读入n和k。
创建一个二维数组t，大小为n*k，用来存储每个成员对每个讨论的观点。
初始化变量maxNum为0，用来记录满足条件的最大剩下成员数量。
遍历所有可能的剩下成员数量x，即x=1或2。
遍历所有讨论，统计同意和不同意的成员数量，分别用变量agree和disagree来记录。
根据条件判断剩下的成员数量是否与x一致，如果一致则更新maxNum的值。
输出maxNum的值。

时间复杂度分析：

遍历所有可能的剩下成员数量x需要O(2)的时间复杂度，遍历所有讨论需要O(k)的时间复杂度，因此总时间复杂度为O(2*k)=O(k)。

空间复杂度分析：

创建的二维数组t需要O(n*k)的空间复杂度。

代码实现如下：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<vector<char>> t(n, vector<char>(k));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < k; j++) {
            cin >> t[i][j];
        }
    }
    int maxNum = 0;
    for (int x = 1; x <= 2; x++) {
        for (int j = 0; j < k; j++) {
            int agree = 0, disagree = 0;
            for (int i = 0; i < n; i++) {
                if (t[i][j] == '+') {
                    agree++;
                } else {
                    disagree++;
                }
            }
            if ((agree >= x && disagree < x) || (agree < x && disagree >= x)) {
                maxNum = max(maxNum, n - disagree);
            }
        }
    }
    cout << maxNum << endl;
    return 0;
}