洛谷P1324题：贪心算法解决矩形分割问题

一、问题分析

我们需要将N×M的木板切割成1×1的小方块，每次切割只能沿横线或竖线进行，且每次切割的代价不同。切割后的木板不能合并，必须分别处理。目标是找到总代价最小的切割方案。

二、算法思路

1.贪心策略‌：每次选择当前代价最大的切割线进行切割

2‌.切割次数‌：横线需要切割N-1次，竖线需要切割M-1次

3‌.交叉影响‌：每次横切会增加后续竖切的次数，反之亦然

三、完整代码

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

int main() {
    int N, M;
    cin >> N >> M;
    
    vector<int> row_cuts(N-1); // 横切代价
    vector<int> col_cuts(M-1); // 竖切代价
    
    // 读取横切代价
    for(int i = 0; i < N-1; ++i) {
        cin >> row_cuts[i];
    }
    
    // 读取竖切代价
    for(int i = 0; i < M-1; ++i) {
        cin >> col_cuts[i];
    }
    
    // 将代价从大到小排序
    sort(row_cuts.begin(), row_cuts.end(), greater<int>());
    sort(col_cuts.begin(), col_cuts.end(), greater<int>());
    
    int row_ptr = 0, col_ptr = 0; // 当前考虑的横切和竖切索引
    int row_segments = 1, col_segments = 1; // 当前木板块的行列数
    long long total_cost = 0;
    
    // 贪心选择当前最大的切割代价
    while(row_ptr < N-1 || col_ptr < M-1) {
        // 选择当前更大的切割代价
        if(row_ptr < N-1 && (col_ptr >= M-1 || row_cuts[row_ptr] > col_cuts[col_ptr])) {
            total_cost += (long long)row_cuts[row_ptr] * col_segments;
            row_segments++; // 横切增加行块数
            row_ptr++;
        } else {
            total_cost += (long long)col_cuts[col_ptr] * row_segments;
            col_segments++; // 竖切增加列块数
            col_ptr++;
        }
    }
    
    cout << total_cost << endl;
    return 0;
}

四、算法详解

1. 输入处理

首先读取木板尺寸N和M，然后读取N-1个横切代价和M-1个竖切代价。

2. 排序预处理

将横切和竖切代价分别从大到小排序，以便后续贪心选择。

3. 贪心选择过程

维护两个指针分别指向当前最大的横切和竖切代价，每次选择较大的那个进行"切割"：

• 选择横切时，总代价增加"当前竖切块数×该横切代价"

• 选择竖切时，总代价增加"当前横切块数×该竖切代价"

4. 块数更新

每次切割后更新相应的块数：

• 横切会增加行块数

• 竖切会增加列块数

五、总结

通过这个问题，我们学习了如何应用贪心算法解决实际切割问题。关键在于识别问题的贪心性质，并设计合适的数据结构和处理流程。这种"每次选择当前最优"的思路在许多优化问题中都有应用，掌握这种解题方法对提升算法能力很有帮助。