2 条题解
-
0
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
- 上传者