问题 F: Mixing Milk 时间限制: 1.000 Sec 内存限制: 128 MB 题目描述 Farming is competitive business -- particularly milk production. Farmer John figures that if he doesn't innovate in his milk production methods, his dairy business could get creamed! Fortunately, Farmer John has a good idea. His three prize dairy cows Bessie, Elsie, and Mildred each produce milk with a slightly different taste, and he plans to mix these together to get the perfect blend of flavors. To mix the three different milks, he takes three buckets containing milk from the three cows. The buckets may have different sizes, and may not be completely full. He then pours bucket 1 into bucket 2, then bucket 2 into bucket 3, then bucket 3 into bucket 1, then bucket 1 into bucket 2, and so on in a cyclic fashion, for a total of 100 pour operations (so the 100th pour would be from bucket 1 into bucket 2). When Farmer John pours from bucket a into bucket b, he pours as much milk as possible until either bucket a becomes empty or bucket b becomes full. Please tell Farmer John how much milk will be in each bucket after he finishes all 100 pours. 输入 The first line of the input file contains two space-separated integers: the capacity c1 of the first bucket, and the amount of milk m1 in the first bucket. Both c1 and m1 are positive and at most 1 billion, with c1≥m1. The second and third lines are similar, containing capacities and milk amounts for the second and third buckets. 输出 Please print three lines of output, giving the final amount of milk in each bucket, after 100 pour operations. 样例输入 Copy 10 3 11 4 12 5 样例输出 Copy 0 10 2 提示 In this example, the milk in each bucket is as follows during the sequence of pours: Initial State: 3 4 5 1. Pour 1->2: 0 7 5 2. Pour 2->3: 0 0 12 3. Pour 3->1: 10 0 2 4. Pour 1->2: 0 10 2 5. Pour 2->3: 0 0 12 (The last three states then repeat in a cycle ...) 枚举问题，用C++

<think>嗯，我现在得解决这个问题，题目是关于三个桶倒牛奶的模拟。题目大意是说，三个桶有不同的容量和初始牛奶量。然后按照1倒到2，2倒到3，3倒到1，这样的循环顺序，进行100次倒的操作。每次倒的时候，要尽可能倒到目标桶满，或者倒空原桶。最后输出每个桶剩下的牛奶量。那我得仔细分析问题，怎么模拟这个过程。 首先，我得理解倒牛奶的规则。比如，当从a倒到b的时候，a桶里的牛奶可能有两种情况：要么倒完，a变成0；要么b被倒满，剩下a的牛奶减少的量等于b的剩余空间。比如，假设a有5单位，b容量是10，当前有3单位。那b还能装10-3=7单位。这时候倒的话，a的5全部倒进去，b变成3+5=8，而a变成0。或者，如果a有8，b剩余空间是5，那么只能倒5单位，这样a剩下3，b满了。 那每次倒的操作，应该怎么做呢？比如，当前a桶有m1，b桶当前有m2，容量是c2。那能倒的数量是min(m1, c2 - m2)。然后，m1减去这个数，m2加上这个数。对吧？ 那这三个桶，每一次倒的顺序是循环的：第一次是1→2，第二次2→3，第三次3→1，第四次1→2，依此类推。所以总共有100次操作。那循环的次数是100次，每次操作对应的倒的顺序是，按1→2，2→3，3→1的循环。那么，每三次为一个周期，然后重复下去。但100次的话，100除以3余数是1，所以最后一次是第100次操作，对应的顺序是第100次的时候，应该属于哪一个倒的顺序？ 比如，操作次数从1到100，每次的顺序应该是这样的：第1次是1→2，第2次是2→3，第3次是3→1，第4次又是1→2，以此类推。那对于第i次操作，i从1开始，那么对应的倒的顺序是（i-1）%3的值来决定。比如，当i%3余1的话，对应的是1→2？或者可能需要具体计算。 比如，i=1，对应的是步骤1→2；i=2，对应步骤2→3；i=3，对应步骤3→1；i=4，对应1→2；i=5，对应2→3；i=6，对应3→1，以此类推。所以，对于每一个步骤i（从1到100），对应的倒的顺序是：当i mod3等于1时，是1→2；等于2时是2→3；等于0时是3→1。或者，应该以i%3的结果来确定？ 例如，i=1，i-1=0，0 mod3=0→对应第一个顺序？或者可能需要更仔细的数学处理。或者可以用一个数组保存每次倒的顺序的源和目标，比如steps数组，每个元素是（源，目标）的pair。比如，步骤的顺序是： 步骤1：1→2 步骤2：2→3 步骤3：3→1 然后步骤4又回到1→2，以此类推。所以对于第k次步骤（k从1开始），对应的源和目标可以通过（k-1）%3来确定索引。例如，建立一个数组：pour_sequence = [(1,2), (2,3), (3,1)]。然后，对于第k次操作，取pour_sequence[(k-1) %3]。这样对吗？ 比如，k=1时，索引是0，对应1→2；k=2时，索引1，对应2→3；k=3时，索引2，对应3→1；k=4时，索引0，对应1→2。这样是正确的。所以这个数组的顺序是正确的。 那现在，我需要用循环模拟这100次操作。每次操作根据当前的步骤选择源和目标，然后进行倒牛奶的操作。 那具体的步骤如何实现呢？比如，可以用三个变量c1, m1；c2, m2；c3, m3。每次根据当前的源和目标，进行操作。比如，当源是a，目标是b的时候，计算可以倒的量amount = min(m_a, c_b - m_b)。然后，m_a -= amount；m_b += amount。 那初始化的时候，输入三个桶的容量和初始牛奶量。然后循环100次，每次确定源和目标，执行倒的操作。 那这样的话，代码的大体结构应该是这样的： 读入c1和m1； 读入c2和m2； 读入c3和m3； 然后循环100次： for i in 0..99: step = i %3 if step ==0: pour from 1 to2 elif step ==1: pour from2 to3 else: pour from3 to1 然后每次pour的操作： 例如，当倒1→2的时候： pour_amount = min(m1, c2 - m2) m1 -= pour_amount m2 += pour_amount 同理其他步骤。 那这样应该就能正确模拟100次操作。那之后输出m1, m2, m3的值。 那现在需要考虑数据范围的问题。题目中的输入可能很大，比如c和m可以是1e9，但是在每次操作中，这些数值的加减不会有问题，因为用int的话，可能会有溢出问题。但在C++中，如果用int的话，1e9的范围，两个相加是可能超过int的最大值的（比如1e9 +1e9=2e9，而int最大是约2e9，如果是32位的话，int的范围是-2^31到2^31-1，即约-2.1e9到2.1e9。所以对于两个1e9的和，可能会溢出。所以应该使用long long类型来存储这些数值。或者题目中给出的条件中，初始时c>=m，并且每次倒入之后，牛奶量不会超过容量。所以每个桶中的牛奶量都是不超过容量的。比如，在倒入的时候，倒入的数量最多是c_b - m_b，所以m_b加上这个数之后不会超过c_b。所以每个桶的牛奶量始终是有效的。所以，如果使用int的话，可能溢出，所以最好使用long long类型。但题目中的样例输出数据比较小，可能没问题，但为了保险，还是用long long处理。 在C++中，输入可以用三个结构体或者数组来保存容量和当前的牛奶量。比如，可以用三个变量： struct Bucket { long long capacity; long long milk; } buckets[3]; 这样，数组索引0对应第一个桶，1对应第二个，2对应第三个。或者，可能更方便的是用数组索引0表示桶1？或者可能更方便的是，让索引与实际编号对应。比如，桶1对应索引0？或者桶1对应索引0？或者根据题目中的编号。比如，题目中的三个桶是1、2、3，所以可能用索引0、1、2分别对应桶1、2、3？或者，为了方便，索引0对应桶1，索引1对应桶2，索引2对应桶3。这样，在操作的时候，当需要处理源a和目标b时，比如步骤是1→2，那么对应的源索引是0，目标索引是1。 然后，pour_sequence数组中的每个元素是源和目标的索引。例如，pour_sequence数组是： pour_orders = [ (0,1), (1,2), (2,0) ] 这样，每个步骤对应的源和目标索引。然后，每次循环i从0到99，总共有100次操作。因为每个循环处理一次倒。那么，步骤的顺序是： 第1次操作（i=0）的时候，取pour_orders[0]，即0→1（对应1→2）。 第2次操作（i=1）的时候，取pour_orders[1%3=1]，即1→2（对应2→3）。 第3次操作（i=2）的时候，取pour_orders[2%3=2]，即2→0（对应3→1）。 第4次操作（i=3）的时候，取pour_orders[3%3=0]，即0→1（1→2）。 这样，循环到i=99的时候，是第100次操作，此时i%3=99%3=0，所以是0→1（即1→2）。 这样，是否正确？ 是的。这样，循环100次，每次i从0到99，i%3的值是0、1、2循环。所以pour_orders数组的顺序是正确的。 那这样，就可以用循环处理每次操作。例如： vector<pair<int, int>> pour_orders = { {0,1}, {1,2}, {2,0} }; for (int i = 0; i < 100; ++i) { int src = pour_orders[i%3].first; int dest = pour_orders[i%3].second; long long amount = min(buckets[src].milk, buckets[dest].capacity - buckets[dest].milk); buckets[src].milk -= amount; buckets[dest].milk += amount; } 这样，每次操作都正确模拟了倒入的过程。 那现在的问题转化为如何正确读取输入，并输出结果。例如，输入的前三行分别是三个桶的容量和当前牛奶量。例如，样例输入： 10 3 11 4 12 5 对应的三个桶： 桶1：c=10，m=3 桶2：c=11，m=4 桶3：c=12，m=5 然后，经过100次倒入操作后的结果，输出三个桶的m值。 那按照上面的模拟方法，是否正确？ 例如，样例中的提示显示，前五次操作后的状态： 初始状态：3 4 5 1次倒入1→2：0 7 5（因为桶1的3全倒入桶2，桶2容量是11，原来4，可以倒入7，所以桶1变为0，桶2变为11？或者原题中的样例输入中，桶2的容量是11吗？ 看样例输入，第二行是11 4，所以容量是11，当前是4。所以当倒入1→2时，桶1的3全部倒入桶2，因为桶2还能装11-4=7。所以倒入3，桶1变为0，桶2变为7。此时，桶2的牛奶量是7，未超过容量。所以第一次倒后的状态是正确的。第二次倒的是2→3，此时桶2有7，桶3的容量是12，当前是5。所以桶3还能装12-5=7。倒入量是min(7,7)=7。所以桶2倒出7，变为0，桶3变为5+7=12。第三次倒3→1，此时桶3的牛奶是12，容量是12？桶3的容量是12？是的。桶1的容量是10，当前是0。所以倒入量是min(12, 10-0)=10。所以倒入10后，桶3剩下2，桶1变为10。此时第三次倒后的状态是10，0，2。第四次倒1→2：此时桶1的10倒入桶2（容量是11，当前是0）。可以倒入11-0=11，但是桶1只有10，所以全部倒入。桶1变为0，桶2变为10。第五次倒2→3：桶2有10，倒入桶3的容量是12，当前是2。所以桶3还能装12-2=10。倒入min(10,10)=10。桶2变为0，桶3变为12。此时状态是0，0，12。第六次倒3→1：倒入桶1的容量是10，当前是0。倒入min(12, 10)=10。桶3剩下2，桶1变成10。此时状态回到第三次的状态。之后每次循环就会重复第三次之后的状态。所以，从第三次到第五次的操作会形成一个循环，周期是三次。所以，100次操作中，前三次是初始到第三次，之后每次三次循环。例如，总共有100次操作，第三次之后剩下的97次操作，其中每三次循环一次。97 ÷3 =32余1。所以，总共有32次完整的周期（每个周期三次操作），加上1次操作。例如，第三次之后是第四次到100次，共97次。其中，每个周期三次，导致状态回到同样的状态。比如，第三次后的状态是10,0,2。第四次操作后是0,10,2；第五次是0,0,12；第六次是10,0,2（第三次的状态）。这样，每三次操作构成一个循环。例如，三次操作后的状态和当前的状态相同。所以，在第三次之后，每三次操作会回到同样的状态。所以，从第三次到第六次，状态恢复。这样，总共有100-3=97次操作。97次操作中，第一次是第四次操作，之后还有96次。96 ÷3=32，刚好。所以，每三次循环，状态回到第三次的状态。因此，整个操作结束后，最后的状态应该等于第三次操作后的状态吗？ 或者，让我们详细计算样例中的操作次数： 初始状态：3 4 5 → step0 操作1→2 →0 7 5 →step1 操作2→3 →0 0 12 →step2 操作3→1 →10 0 2 →step3 操作1→2 →0 10 2 →step4 操作2→3 →0 0 12 →step5 操作3→1 →10 0 2 →step6 操作1→2 →0 10 2 →step7 ... 可以看到，从step3之后，每三次操作（步骤4、5、6）之后，状态回到10 0 2。即，步骤3、6、9等之后的状态都是10 0 2。例如，步骤3是第三次操作，之后每三个步骤（步骤4、5、6）执行后，步骤6的第三次操作会回到同样的状态。这样，当总共有100次操作时，第三次操作后的次数是97次。这个时候，97次操作中有多少次完整的周期？ 比如，第三次操作后的次数是100-3=97次。这些97次操作中，每三个步骤为一个周期，导致状态回到原来的状态。所以，如果这三个步骤后状态不变，那么每个周期相当于0次变化。因此，97次操作等于3*32 +1次。即，32个完整周期（32*3=96次操作），剩下的1次操作。因此，总的状态等于第三次操作后的状态（10,0,2）加上这1次操作后的状态。比如，第三次后的状态是10,0,2。那么，后续的96次操作（即32个周期）之后，状态还是10,0,2。然后剩下的1次操作是第96+3+1=100次？或者，第三次操作是第3次，之后的步骤是第4到第100次，共97次。其中，前96次是32个周期，之后还剩1次。所以，第3+96=99次操作时，状态是10,0,2。剩下的第100次操作是第100次，对应步骤（i=99）时，i%3=99%3=0，所以操作是1→2。此时，将10倒入到2。桶1中的牛奶是10，桶2的容量是11，当前是0。可以倒入min(10, 11-0)=10。所以，倒入后，桶1变成0，桶2变成10。此时，状态是0,10,2。这与样例的输出结果不符。样例的输出是0，10，2。那这说明，当100次操作之后，状态是0,10,2？ 这可能与我的之前的分析矛盾。比如，在样例中，步骤4、5、6之后，状态变成0,10,2 →0,0,12 →10,0,2。这三个步骤构成一个周期吗？或者说，步骤4、5、6之后，状态又回到步骤3后的状态？ 比如，步骤3后的状态是10,0,2。 步骤4（1→2）：倒入10，倒入桶2的容量是11。所以，桶1的10全部倒入桶2。此时，桶1变成0，桶2变成10。此时状态是0,10,2。 步骤5（2→3）：桶2的10倒入桶3。桶3的容量是12，当前是2，可以倒入10。所以，桶2倒出10，桶3变成12。此时，状态是0,0,12。 步骤6（3→1）：桶3的12倒入桶1。桶1的容量是10，倒入10，桶3剩下2。此时，状态是10,0,2。这与步骤3后的状态相同。 所以，步骤4、5、6这三个操作之后，状态回到步骤3的状态。因此，这三个操作构成一个循环周期，每三次操作之后状态复原。所以，每次执行这三个操作，状态回到10,0,2。然后，当总共有100次操作时，第三次操作之后，剩下的97次操作中，有多少次这样的周期？ 第三次操作是第3次操作（i=2）。然后，剩下的次数是100-3=97次。在这97次中，每三个操作构成一个周期，使得状态复原。所以，97次操作可以分为32个完整的周期（32*3=96次），剩下的1次操作。32个周期之后，状态还是步骤3后的状态，即10,0,2。剩下的1次操作是步骤的第3+96+1=100次操作。此时，执行的是步骤i=99（因为循环变量是0到99），对应的操作是1→2。此时，将桶1的10倒入桶2。桶1的牛奶是10，桶2的容量是11，当前牛奶是0。倒入10后，桶1变为0，桶2变为10。此时，状态是0,10,2。这正是样例的输出。所以，这说明，经过100次操作后的最终状态是0,10,2。而样例的输出结果正确。 所以，这说明我的模拟方法是对的。那这个时候，正确的代码应该如何处理？ 因此，正确的代码结构应该是： 读取三个桶的容量和初始牛奶量。 模拟100次倒入操作，每次按顺序1→2，2→3，3→1循环。每次倒入时，计算倒入的量，并更新两个桶的牛奶量。 最后输出三个桶的牛奶量。 在C++中，可以用三个结构体变量，或者数组来处理。比如，用数组保存每个桶的容量和当前牛奶量： long long c[3], m[3]; 输入： cin >> c[0] >> m[0]; cin >> c[1] >> m[1]; cin >> c[2] >> m[2]; 然后，对于每个操作步骤，从0到99： for (int i =0; i <100; i++){ int src, dest; if (i%3 ==0) { src=0; dest=1;} //步骤1→2对应i%3=0（i从0开始） else if (i%3 ==1) {src=1; dest=2;} //步骤2→3 else {src=2; dest=0;} //步骤3→1 int amount = min(m[src], c[dest]-m[dest]); m[src] -= amount; m[dest] += amount; } 然后，输出m[0]、m[1]、m[2]。 这样就能得到正确的结果。 那这样处理样例输入的话，是否正确？ 样例输入的初始状态是： m = [3,4,5] 循环处理100次： 每次操作按顺序1→2、2→3、3→1。 比如，第100次操作是i=99。此时，i%3=0，所以src=0，dest=1。此时，m[0]的值是多少？ 在第三次操作之后，状态变为10,0,2。之后每次三个步骤循环。总共有97次操作。97次中的前96次是32个周期，每个周期三次，状态不变。所以，在96次之后，状态还是10,0,2。剩下的1次操作是i=99，对应步骤0→1（即1→2）。此时，将10倒入到桶2。桶2的容量是11，当前是0。所以倒入10，m[0]变为0，m[1]变为10。此时，最终状态是0,10,2。符合样例的输出。 所以，这样的代码是正确的。 那现在需要注意的是，在C++中，数据类型的正确性。比如，当输入的c和m可能很大时，使用int可能会导致溢出。因此，应该使用long long类型存储。 因此，在代码中，将c和m声明为long long数组。 综上，正确的C++代码应该是： #include <iostream> #include <algorithm> using namespace std; int main() { long long c[3], m[3]; for (int i=0; i<3; i++) { cin >> c[i] >> m[i]; } for (int i=0; i<100; i++) { int src, dest; if (i%3 ==0) { src=0; dest=1; } else if (i%3 ==1) { src=1; dest=2; } else { src=2; dest=0; } long long pour = min(m[src], c[dest] - m[dest]); m[src] -= pour; m[dest] += pour; } for (int i=0; i<3; i++) { cout << m[i] << endl; } return 0; } 这样，就可以正确模拟100次倒入操作，得到正确的结果。</think>要解决这个问题，我们需要模拟三个桶之间按照特定顺序倒入牛奶的过程，共进行100次操作。每次操作将尽可能多的牛奶从一个桶倒入另一个桶，直到源桶为空或目标桶满。最终需要输出每个桶中的牛奶量。 ### 方法思路 1. **问题分析**： - 三个桶的容量和初始牛奶量各不相同。 - 每次按照1→2、2→3、3→1的顺序循环倒入牛奶。 - 每次倒入的量为源桶的牛奶量和目标桶剩余容量的较小值。 2. **关键步骤**： - 读取三个桶的容量和初始牛奶量。 - 模拟100次倒入操作，每次操作根据当前步骤选择源桶和目标桶。 - 计算倒入量并更新源桶和目标桶的牛奶量。 3. **优化与注意点**： - 使用循环来处理100次操作，每次操作通过取模运算确定当前的倒入顺序。 - 使用长整型（`long long`）来避免溢出问题。 ### 解决代码 ```cpp #include <iostream> #include <algorithm> using namespace std; int main() { long long c[3], m[3]; for (int i = 0; i < 3; ++i) { cin >> c[i] >> m[i]; } for (int step = 0; step < 100; ++step) { int src = step % 3; int dest = (src + 1) % 3; if (src == 2) dest = 0; // 当src是2时，目标应为0 long long pour = min(m[src], c[dest] - m[dest]); m[src] -= pour; m[dest] += pour; } for (int i = 0; i < 3; ++i) { cout << m[i] << endl; } return 0; } ``` ### 代码解释 1. **输入处理**： - 使用数组`c`和`m`分别存储三个桶的容量和当前牛奶量。 2. **循环处理100次倒入操作**： - 根据当前步骤确定源桶和目标桶。例如，第0步对应1→2，第1步对应2→3，第2步对应3→1，依此类推。 - 计算每次倒入的牛奶量，并更新源桶和目标桶的牛奶量。 3. **输出结果**： - 循环结束后，依次输出三个桶中的牛奶量。 该方法通过简单的循环和取模运算高效地模拟了100次倒入操作，确保了正确性和性能。