题解：CF2122B Pile Shuffling

Chenxuhang_play · 2025-08-04 18:57:18 · 题解

题目大意

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

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

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

思路

需要分开计算 0 和 1 所需要的操作次数。

0 的移动次数

如果 a_i>c_i，那么现在要把多余的 0 放到其他堆去，此时需要移动 a_i-c_i 次。

如果 a_i<c_i，那么现在要从其它堆取 0 放到第 i 堆，此时需要操 c_i-a_i 次。

1 的移动次数

如果 b_i>d_i，那么现在要把多余的 1 放到其他堆去，但是要先把上方的 0 移到堆的中间，所以要先操作 a 次（此时不需要除以 2，因为这次操作发生在同一堆内，所以不会被重复计算），再操作 b_i-d_i 次。

如果 b_i<d_i，那么现在只要从其它堆取 1 放到第 i 堆即可，此时需要操作 d-b_i 次。

注意事项

• 注意由于每次操作会在不同的两个堆内被算，所以最后的结果需要除以 2，才是最终的答案。

• 多测不清空，爆零两行泪。

• 十年 OI 一场空，不开 long long 见祖宗。

关键代码

cin>>n;
sum=0;
for(int i=0;i<n;i++)
{
  cin>>a>>b>>c>>d;
  if(a>c) sum+=a-c;
  else if(a<c) sum+=c-a;
  if(b>d) sum+=b-d+a*2;
  else if(b<d) sum+=d-b;
}
cout<<sum/2<<endl;