题解：水壶问题（Jugs）

题目分析

本题要求通过一系列操作（装满、倒空、倒灌）在两个互质容量的水壶中，使其中一个水壶恰好装有目标水量。核心在于利用数论中互质的性质，通过模拟倒水过程找到最短操作序列。

方法思路

1. 问题特性：当两个水壶容量互质时，根据贝祖定理，它们的线性组合可以表示任意整数。因此，目标水量N必然可以通过若干次装满、倒空和倒灌操作得到。
2. 操作策略：
   • 优先装满小水壶：由于水壶容量互质，重复装满小水壶并倒入大水壶，直到大水壶满后倒空，最终可在小水壶或大水壶中得到目标水量。
   • 模拟倒灌过程：每次将小水壶的水倒入大水壶，若大水壶满则倒空，重复此过程直至目标达成。

解决代码

#include<iostream>
using namespace std;

int main() {
    int Ca, Cb, N; // Ca为小水壶容量，Cb为大水壶容量，N为目标水量
    while (cin >> Ca >> Cb >> N) {
        int a = 0, b = 0; // a: 小水壶水量，b: 大水壶水量
        vector<string> steps; // 记录操作步骤

        while (b != N) {
            // 装满小水壶
            steps.push_back("fill A");
            a = Ca;
            
            // 将小水壶的水倒入大水壶
            int pour = min(a, Cb - b);
            a -= pour;
            b += pour;
            steps.push_back("pour A B");
            
            // 如果大水壶满了，倒空它
            if (b == Cb) {
                steps.push_back("empty B");
                b = 0;
            }
        }

        steps.push_back("success"); // 目标达成
        
        // 输出所有步骤
        for (const string& step : steps) {
            cout << step << endl;
        }
    }
    return 0;
}

代码解释

1. 输入处理：循环读取每个测试用例的三个整数Ca、Cb、N，其中Ca为小水壶容量，Cb为大水壶容量。
2. 状态初始化：用变量a和b分别记录小水壶和大水壶的当前水量，初始均为0。
3. 操作模拟：
   • 装满小水壶：执行fill A操作，将小水壶水量设为Ca。
   • 倒灌至大水壶：计算可倒入大水壶的最大水量（避免溢出），更新两水壶水量，并记录pour A B操作。
   • 倒空大水壶：若大水壶已满（b == Cb），执行empty B操作，将大水壶水量清零。
4. 终止条件：当大水壶水量b等于目标值N时，终止循环，添加success步骤并输出所有操作。

复杂度分析

• 时间复杂度：每次操作至少改变一个水壶的状态，状态空间为Ca × Cb，最坏情况下需要遍历所有状态，时间复杂度为O(Ca × Cb)。
• 空间复杂度：使用向量存储操作步骤，最多存储O(Ca × Cb)个步骤，空间复杂度为O(Ca × Cb)。

该方法利用互质性质确保了操作的有效性，通过模拟倒水过程直观地解决了问题，适用于所有满足条件的输入。