2 条题解

  • 0
    @ 2025-4-9 20:15:20

    24分的代码:

    #include <iostream>
    #include <vector>
    #include <climits>
    #include <algorithm>
    using namespace std;
    
    // 函数用于生成图腾
    vector<string> generateTotem(int n) {
        if (n == 1) {
            return {" /\\", "/__\\"};
        }
        vector<string> prevTotem = generateTotem(n - 1);
        int prevHeight = prevTotem.size();
        int prevWidth = prevTotem[0].size();
        vector<string> newTotem(2 * prevHeight);
        // 处理上半部分
        for (int i = 0; i < prevHeight; ++i) {
            newTotem[i] = string(prevWidth, ' ') + prevTotem[i];
        }
        // 处理下半部分
        for (int i = 0; i < prevHeight; ++i) {
            newTotem[prevHeight + i] = prevTotem[i] + " " + prevTotem[i];
        }
        return newTotem;
    }
    
    // 多米诺骨牌问题的函数
    int minFlipsToMinDifference(int n, vector<pair<int, int>>& dominoes) {
        int topSum = 0, bottomSum = 0;
        for (const auto& domino : dominoes) {
            topSum += domino.first;
            bottomSum += domino.second;
        }
        int minDiff = INT_MAX;
        int minFlips = 0;
        // 枚举所有可能的翻转组合
        for (int mask = 0; mask < (1 << n); ++mask) {
            int currentTopSum = topSum, currentBottomSum = bottomSum;
            int currentFlips = 0;
            for (int i = 0; i < n; ++i) {
                if (mask & (1 << i)) {
                    currentTopSum = currentTopSum - dominoes[i].first + dominoes[i].second;
                    currentBottomSum = currentBottomSum - dominoes[i].second + dominoes[i].first;
                    currentFlips++;
                }
            }
            int currentDiff = abs(currentTopSum - currentBottomSum);
            if (currentDiff < minDiff || (currentDiff == minDiff && currentFlips < minFlips)) {
                minDiff = currentDiff;
                minFlips = currentFlips;
            }
        }
        return minFlips;
    }
    
    int main() {
        int n;
        cin >> n;
        vector<pair<int, int>> dominoes(n);
        for (int i = 0; i < n; ++i) {
            cin >> dominoes[i].first >> dominoes[i].second;
        }
        int result = minFlipsToMinDifference(n, dominoes);
        cout << result << endl;
        return 0;
    }
    

    信息

    ID
    135
    时间
    1000ms
    内存
    256MiB
    难度
    9
    标签
    递交数
    61
    已通过
    3
    上传者