CF2122B Pile Shuffling

· · 题解

题目传送门

题目大意

有 n 个二进制堆，其中第 i 个堆顶部有 a_i 个 0，b_i 个 1。

每次操作中，你可以取出任意堆的顶部元素，并将其移动到任意堆的任意位置（包括原堆）。

计算最少需要多少次操作，才能使第 i 个堆形成顶部 c_i 个 0 和底部 d_i 个 1 的目标状态。

思路

我们需要分别考虑 0 和 1 的数量。

0 的数量

  1. 如果第 i 堆 0 的初始数量大于 0 的目标数量，即 a_i > c_i，那么现在要把多余的 0 放到其他堆去，此时需要操作 a_i - c_i 次。
  2. 如果第 i 堆 0 的初始数量小于 0 的目标数量，即 a_i < c_i，那么现在要从其它堆取 0 放到第 i 堆，此时需要操作 c_i - a_i 次。

注意上述操作的操作次数需要除以 2，因为将数字从一个堆放到另一个堆会被计算两次。例如有两个堆，第一个堆有 5 个 0，目标状态为 4 个 0。第二个堆有 3 个 0，目标状态为 4 个 0。此时只需要将第一个堆的一个 0 放在第二个堆即可，只用了一次操作。但要是按照上述操作则需要 2 次操作，所以操作次数要除以 2。

1 的数量

  1. 如果第 i 堆 1 的初始数量大于 1 的目标数量，即 b_i > d_i，那么现在要把多余的 1 放到其他堆去，但是要先把上方的 0 移到堆的中间，所以要先操作 c_i 次（此时不需要除以 2，因为这次操作发生在同一堆内，所以不会被重复计算），再操作 b_i - d_i 次。
  2. 如果第 i 堆 1 的初始数量小于 1 的目标数量，即 b_i < d_i，那么现在只要从其它堆取 1 放到第 i 堆即可，此时需要操作 d_i - b_i 次。

同理，上述操作的操作次数需要除以 2。

关键代码

long long sum=0;
if(a>c) sum+=(a-c);
else if(a<c) sum+=(c-a);
if(b>d) sum+=(c*2) , sum+=(b-d);
else if(b<d) sum+=(d-b);
cout <<sum/2;