贪心 - 2019.11.5 咒语

题面

【题目描述】

亮亮梦到自己来到了魔法城堡，但一扇巨大的石门阻拦了他通向城堡内的路。

正当他沮丧之际，突然发现门上有一处机关，机关上有一张很长的纸条。 亮亮拿起纸条的一端，只见上面写着打开机关的方法：“打开机关需要念动符咒，咒语是一串长为 \(L\) 的由 \(0\) 和 \(1\) 组成的字符串。在这张长纸条上列了 \(n\) 个长为 \(L\) 的字符串，正确的咒语即是在纷繁的 \(2^L\) 种字符串中，与这些纸条上的 字符串相异度之和最小，并且在满足这一条件下，\(0\) 的个数最多的字符串。两个字符串的相异度定义为对应位置不相等的字符对的个数。如 ‘011’ 和 ‘001’ 的 相异度为 \(1\)，因为它们有且只有第二个位置上的字符不相等。”

亮亮拉起纸条，只觉得纸条似乎永远也拉不完。这上面有着数以万计的字符串，而每一个字符串的长度也或百或千，以人力看来是无法得到正确的咒语。你能帮帮他，让他得以进入魔法城堡，一窥其中的奥秘吗？

【输入格式】

第一行为一个数字 \(N\) 。

接下来的 \(N\) 行，每行为一个长为 \(L\) 的 01 字符串。数据保证 \(N\) 个字符串等长。

【输出格式】

只有一行，是一个长为 \(L\) 的字符串 \(S\)，即为正确的咒语。

【样例输入】

4
01011
01001
01101
10111

【样例输出】

01001

【数据规模】

对于 \(20\%\) 的数据，\(N\le 5\)；

对于 \(60\%\) 的数据，\(N\le 100\)；

对于 \(100\%\) 的数据，\(1\le N\le 1000\)，\(1\le L\le 1000\)。

解

对每个 \(S_i\)，考虑 \((A_{ji})_{i=1}^n\) 中 0、1 的个数，取多的即可（若相等，取 0）。

程序

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
 
int n, c[1000][1000], l, ans[1000];
char s[1050][1050];
 
int main() {
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> s[i];
    l = strlen(s[0]);
     
    for (int i = 0; i < n; i++)
        for (int j = 0; j < l; j++)
            c[i][j] = s[i][j] - '0';
     
    for (int i = 0; i < l; i++) {
        // considering ans[i]
        int zc = 0, oc = 0;
        for (int j = 0; j < n; j++)
            if (c[j][i] == 0)
                zc++;
            else oc++;
        if (oc > zc) ans[i] = 1;
        else ans[i] = 0;
    }
     
    for (int i = 0; i < l; i++)
        cout << ans[i];
    cout << endl;
     
    return 0;
}

贪心 - 2019.11.5 咒语

原文：https://www.cnblogs.com/lrw04/p/11826344.html