华为od机试统一考试B卷 C++【雨花石难题】

曾经终败给现在 2023-10-15 08:09 8阅读 0赞

### 题目 ###

![在这里插入图片描述][2eda5041be1c47b59761c2b944511c42.png]

### 代码 ###

#include <iostream>
    #include <vector>
    #include <algorithm>
    
    using namespace std;
    
    int checkSplit(int stoneCount, vector<int>& stoneWeights) {
        
        int totalWeight = 0;
    
        // 计算所有雨花石的总重量
        for (int weight : stoneWeights) {
        
            totalWeight += weight;
        }
    
        // 如果重量之和不能被2整除，则不可能平分
        if (totalWeight % 2 != 0) {
        
            return -1;
        }
    
        int halfWeight = totalWeight / 2;  // 平分后的每一份的重量
        // 初始化动态规划表，用于存储达到每一个重量所需的最小雨花石数量
        vector<vector<int>> dpTable(stoneCount + 1, vector<int>(halfWeight + 1, stoneCount));
    
        dpTable[0][0] = 0;
    
        // 动态规划过程
        for (int i = 1; i <= stoneCount; i++) {
        
            int currentWeight = stoneWeights[i - 1];
            for (int j = 0; j <= halfWeight; j++) {
        
                if (j < currentWeight) {
        
                    dpTable[i][j] = dpTable[i - 1][j];
                } else {
        
                    // 两种选择：不拿当前的雨花石或拿当前的雨花石
                    int option1 = dpTable[i - 1][j];
                    int option2 = dpTable[i - 1][j - currentWeight] + 1;
                    // 选择需要雨花石数量较少的那一个
                    dpTable[i][j] = min(option1, option2);
                }
            }
        }
    
        // 判断是否能够使用所有的雨花石达到halfWeight
        if (dpTable[stoneCount][halfWeight] == stoneCount) {
        
            return -1;
        }
    
        // 计算结果，选择拿或者不拿数量较小的那一边
        return min(stoneCount - dpTable[stoneCount][halfWeight], dpTable[stoneCount][halfWeight]);
    }
    
    int main() {
        
        int stoneCount;
        cin >> stoneCount;
    
        vector<int> stoneWeights(stoneCount);
        for (int i = 0; i < stoneCount; i++) {
        
            cin >> stoneWeights[i];
        }
    
        int result = checkSplit(stoneCount, stoneWeights);
        cout << result << endl;
    
        return 0;
    }

[2eda5041be1c47b59761c2b944511c42.png]: https://img-blog.csdnimg.cn/2eda5041be1c47b59761c2b944511c42.png