UVa 1622 Robot

寂静山林

329人浏览 · 2026-10-03 14:24:20

寂静山林 · 2026-10-03 14:24:20 发布

题目描述

在一个 $\times M$ 的网格中，每个格子都放有一个机器人。这些机器人可以执行四种命令：

NORTH：所有机器人向上（北）移动一格；
SOUTH：所有机器人向下（南）移动一格；
WEST：所有机器人向左（西）移动一格；
EAST：所有机器人向右（东）移动一格。

执行一条命令时，如果某个机器人移出了网格，它会被立即摧毁，且之后无法再执行任何命令。
给定每种命令的总数，你可以任意安排这些命令的执行顺序，目标是使得所有机器人实际执行命令的总次数最大化。

输入格式

输入包含多组测试数据。
每组数据第一行包含两个正整数 $N$ 和 $M$ （ $\le N, M \le 10^5$ ），分别表示网格的行数和列数。
第二行包含四个整数，依次为 NORTH、SOUTH、WEST、EAST 四种命令的数量，每个数均不超过 $10^5$ 。
输入以一行 0 0 结束。

输出格式

对于每组数据，输出一行 Case X: Y，其中 $X$ 是测试用例编号（从 $1$ 开始）， $Y$ 是最大总执行次数。答案保证在 $64$ 位有符号整数范围内。

样例

输入

输出

Case 1: 4
Case 2: 9

题目分析

所有机器人同时执行同一条命令。在某条命令执行之前，如果历史上向北移动的总位移最大值为 $max⁡R\max R$ ，最小值为 $min⁡R\min R$ ，则行方向的历史跨度（最大最小位移之差）为 $Rspan=max⁡R−min⁡RR_{\textit{span}} = \max R - \min R$ 。同理定义列方向的历史跨度 $CspanC_{\textit{span}}$ 。
此时，所有存活机器人的行坐标必须位于 $R_{\textit{span}}]$ 范围内，列坐标必须位于 $C_{\textit{span}}]$ 范围内，因此当前存活的机器人数量为：

$\textit{cur} = (N - R_{\textit{span}}) \times (M - C_{\textit{span}})$

执行每一条命令前，所有存活机器人都会执行它，因此该命令的贡献就是当前的 $cur\textit{cur}$ 。一旦某个方向的跨度达到其网格尺寸（例如 $Rspan≥NR_{\textit{span}} \ge N$ ），则 $cur\textit{cur}$ 变为 $0$ ，之后所有命令的贡献均为 $0$ 。

问题转化为：给定四种移动指令的数量，如何安排顺序，使得每一步的 $cur\text{cur}$ 累加和最大。

观察发现，相反方向的成对指令（如 NORTH 和 SOUTH）如果交替执行，其历史跨度只会从 $0$ 变为 $1$ ，之后不会继续增加。这种“配对”的指令收益高且不压缩后续空间，应优先执行。
当某一方向的两种相反指令数量不等时，剩余的单向指令会迫使跨度逐步增加。此时应选择当前剩余空间更大的方向执行，即比较 $R_{\textit{span}}$ 与 $C_{\textit{span}}$ ，优先执行空间较大者。

解题思路

1. 统一方向，简化判断

对于每一组数据，我们先将南北、东西两对方向的数量整理为“大数”和“小数”，使得：

$\textit{cntNorth} \ge \textit{cntSouth}, \quad \textit{cntWest} \ge \textit{cntEast}$

这样，配对数量即为较小的那个数，剩余单向指令为两者的差。

2. 决定先处理哪个方向的配对

先处理东西配对还是南北配对会影响后续的剩余空间，因此需要分别估算两种顺序的总收益，并选择较大的那个。

定义：

如果先执行东西配对（共 $cntEast\textit{cntEast}$ 对），每一对（两条指令）执行后，列跨度变为 $1$ ，收益为 $\times (M-1)$ （除第一对的第一条收益为 $\times M$ 外），随后处理剩余的 WEST 指令，再处理南北配对及剩余 NORTH 指令。
同理，先执行南北配对也有对应的收益估算。

我们通过两个表达式 gainFirstEW 和 gainFirstNS 分别计算两种顺序的预估值，若先南北更优，则交换 $N$ 与 $M$ ，同时交换南北与东西的计数，使得后续代码统一按“先东西后南北”处理。

3. 执行东西配对与多余西向指令

若存在 $cntEast>0\textit{cntEast} > 0$ ，执行 $ \text{cntEast}$ 对东西交替指令，收益为：

$\cdot N \cdot \textit{cntEast} \cdot 2$

其中第一对的第一条收益为 $N$ ，之后每对两条指令的收益均为 $\times (M-1)$ 。
然后处理剩余的 WEST 指令（即 cntWest -= cntEast）。若还有剩余，执行一条 WEST，收益为 $\times M$ ，列跨度变为 $1$ ，同时有效列数 $M$ 减 $1$ 。
将剩余的 WEST 指令数限制为不超过当前有效列数，因为超过部分执行时收益为 $0$ 。

4. 循环处理剩余的 `WEST` 和 `NORTH`（可能还有 `SOUTH`）

此时，EAST 已清空，SOUTH 可能仍然存在（如果 cntNorth >= cntSouth）。
在每一步，若 SOUTH > 0，则有两种选择：

开始执行南北配对（消耗掉所有 SOUTH 以及与之一一配对的 NORTH），这会使行跨度变为 $1$ ，有效行数 $N$ 减 $1$ ，并可能留下剩余 NORTH；
继续执行一条 WEST，列跨度继续增加。

计算两种选择的预估收益，选择收益更大的方案。若没有 WEST 指令，则只能执行南北配对。

当 SOUTH 清空后，只剩下 WEST 和 NORTH 两种单向指令。此时，每一步选择当前剩余空间更大的方向执行（即比较当前有效行数和列数），若行数大则执行 NORTH，否则执行 WEST。

如果只剩一种方向（如只有 NORTH），则连续执行该方向的指令，收益形成一个等差数列，可直接用公式求和：

$\text{收益} = \text{列数} \times \text{剩余指令数} \times \frac{2 \times \text{行数} - \text{剩余指令数} + 1}{2}$

同理处理只剩 WEST 的情况。

5. 正确性说明

贪心选择的正确性基于以下事实：

配对指令不增加历史跨度，应尽早执行，因为越早执行收益越大（此时剩余空间最多）。
当必须增加某一方向的跨度时，选择剩余空间更大的方向执行，可以使得当前的 $R_{\text{span}}) \times (M - C_{\text{span}})$ 尽可能大，从而保证每一步都取得局部最优，且该贪心策略可通过交换论证证明其全局最优。

6. 复杂度分析

每组数据只需要常数次算术运算和循环，循环次数等于实际可执行的指令数，但指令总数不超过 $\times 10^5$ ，因此时间复杂度为 $O(总指令数)O(\text{总指令数})$ 。
空间复杂度 $O (1)$ 。

代码实现

// Robot
// UVa ID: 1622
// Verdict: Accepted
// Submission Date: 2026-06-25
// UVa Run Time: 0.000s
//
// 版权所有（C）2026，邱秋。metaphysis # yeah dot net

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

int main() {
    LL nRows, nCols;                 // 行数、列数
    int caseNo = 1;
    while (cin >> nRows >> nCols, nRows || nCols) {
        LL cntNorth, cntSouth, cntWest, cntEast;
        cin >> cntNorth >> cntSouth >> cntWest >> cntEast;
        LL answer = 0;

        // 保证 cntNorth >= cntSouth, cntWest >= cntEast
        if (cntNorth < cntSouth) swap(cntSouth, cntNorth);
        if (cntWest < cntEast) swap(cntEast, cntWest);

        // 计算两种优先顺序的预估收益，决定先东西还是先南北
        LL gainFirstEW = nRows + (nCols - 1) * nRows * cntEast * 2
                       + (nCols - 1) + (nCols - 1) * (nRows - 1) * cntSouth * 2;
        LL gainFirstNS = nCols + nCols * (nRows - 1) * cntSouth * 2
                       + (nRows - 1) + (nCols - 1) * (nRows - 1) * cntEast * 2;

        if (cntWest - cntEast) {
            gainFirstEW += (nCols - 1) * nRows;
            gainFirstNS += (nCols - 1) * (nRows - 1);
        }
        if (cntNorth - cntSouth) {
            gainFirstEW += (nCols - 1) * (nRows - 1);
            gainFirstNS += nCols * (nRows - 1);
        }

        // 若先南北更优，则交换行列及对应的方向计数
        if (gainFirstEW < gainFirstNS) {
            swap(nRows, nCols);
            swap(cntNorth, cntWest);
            swap(cntSouth, cntEast);
        }

        bool hasExecutedEWPair = true;   // 是否已执行过东西配对

        // 执行东西配对（cntEast 对）
        if (cntEast) {
            answer += nRows + (nCols - 1) * nRows * cntEast * 2;
            cntWest -= cntEast;
            cntEast = 0;
            --nCols;
            hasExecutedEWPair = false;
        }

        // 处理多余的向西指令
        if (cntWest) {
            answer += nCols * nRows;
            --cntWest;
            if (hasExecutedEWPair) --nCols;
        }

        // 超过列数的向西指令无法执行，截断
        cntWest = min(nCols, cntWest);

        // 处理剩余的西向和北向指令（可能还有南向）
        while (cntWest || cntNorth) {
            if (cntSouth) {
                // 比较“先南北配对”与“继续向西”的收益
                LL t1 = nCols * nRows + (nRows - 1) * nCols * 2 * cntSouth;
                LL t2 = nCols * nRows + (nCols - 1) * nRows
                      + (nCols - 1) * (nRows - 1) * (2 * cntSouth - 1);
                if (cntNorth - cntSouth) {
                    t1 = nCols * nRows + (nRows - 1) * nCols * (2 * cntSouth + 1);
                    t2 = nCols * nRows + (nCols - 1) * nRows
                       + (nCols - 1) * (nRows - 1) * 2 * cntSouth;
                }
                if (t1 > t2 || !cntWest) {
                    // 执行南北配对
                    answer += nCols + nCols * (nRows - 1) * cntSouth * 2;
                    cntNorth -= cntSouth;
                    cntSouth = 0;
                    --nRows;
                    if (cntNorth) {
                        answer += nCols * nRows;
                        --cntNorth;
                    }
                    cntNorth = min(nRows, cntNorth);
                } else {
                    // 继续向西
                    answer += nCols * nRows;
                    --nCols;
                    --cntWest;
                }
            } else if (!cntWest) {
                // 仅剩北向，等差数列
                answer += nCols * cntNorth * (2 * nRows - cntNorth + 1) / 2;
                cntNorth = 0;
            } else if (!cntNorth) {
                // 仅剩西向，等差数列
                answer += nRows * cntWest * (2 * nCols - cntWest + 1) / 2;
                cntWest = 0;
            } else {
                // 两者都有，选择剩余空间较大的方向
                answer += nCols * nRows;
                if (nCols > nRows) {
                    --nCols;
                    --cntWest;
                } else {
                    --nRows;
                    --cntNorth;
                }
            }
        }

        cout << "Case " << caseNo++ << ": " << answer << endl;
    }
    return 0;
}