P1324 矩形分割

简单的贪心题。

因为要切成 \(1\times 1\) 的小方块，所以这 \((n-1)+(m-1)\) 条线的每条线都会挨一刀，只需要将顺序确定下来，就有可能计算出总代价。

贪心地考虑，对于同一侧来说，代价大的切割要尽早处理，否则一旦在另一个方向上进行了一次切割，这一刀的代价就会增加一倍，代价小的加倍总比代价大的加倍要优，所以我们可以直接把横、竖线切割的代价分别从大到小排序；而对于一横一竖两刀来说，同理应该先切代价大的。于是想到可以用两个指针按照上述方案同步扫描排序后的两个数组，统计答案。

因为“不能把两块木板拼起来切割”，所以每横着切一刀的费用 \(a_i\) 要乘一个系数，即 \(竖着切的刀数+1\)；每竖着切一刀的费用 \(b_i\) 也要乘一个系数，即 \(横着切的刀数+1\)。不妨开两个变量，在指针扫描的同时统计两个方向各切了多少刀，即可统计出答案。

下面是 AC 代码：

#include <bits/stdc++.h>

using i64 = long long;

bool compare(int x, int y)
{
    return x > y;
}

int main()
{
    int n, m;
    std::cin >> n >> m;
    std::vector<i64> rowCutCosts(n - 1);
    std::vector<i64> columnCutCosts(m - 1);
    for (int i = 0; i < n - 1; i++)
    {
        std::cin >> rowCutCosts[i];
    }
    for (int i = 0; i < m - 1; i++)
    {
        std::cin >> columnCutCosts[i];
    }

    std::sort(rowCutCosts.begin(), rowCutCosts.end(), compare);
    std::sort(columnCutCosts.begin(), columnCutCosts.end(), compare);

    i64 sumCost = 0;
    int i = 0, j = 0;
    while (i < n - 1 && j < m - 1)
    {
        if (rowCutCosts[i] >= columnCutCosts[j])
        {
            sumCost += (i64)rowCutCosts[i++] * (j + 1);
        }
        else
        {
            sumCost += (i64)columnCutCosts[j++] * (i + 1);
        }
    }
    for (; i < n - 1; i++)
    {
        sumCost += (i64)rowCutCosts[i] * (j + 1);
    }
    for (; j < m - 1; j++)
    {
        sumCost += (i64)columnCutCosts[j] * (i + 1);
    }
    std::cout << sumCost << '\n';
    return 0;
}

注意输入数据是 \(n-1,m-1\) 个数！

THE END