专栏文章

题解：CF2122B Pile Shuffling

CChenxuhang_play
CF2122B题解参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mioiy3tx
此快照首次捕获于
2025/12/02 19:58
3 个月前
此快照最后确认于
2025/12/02 19:58
3 个月前
查看原文

题目大意

有 nn 个二进制堆，其中第 ii 个堆顶部有 aia_i 个 00，bib_i 个 11。
每次操作中，你可以取出任意堆的顶部元素，并将其移动到任意堆的任意位置（包括原堆）。
计算最少需要多少次操作，才能使第 ii 个堆形成顶部 cic_i个 00 和底部 did_i 个 11 的目标状态。

思路

需要分开计算 00 和 11 所需要的操作次数。

00 的移动次数

如果 ai>cia_i>c_i，那么现在要把多余的 00 放到其他堆去，此时需要移动 ai−cia_i-c_i 次。
如果 ai<cia_i<c_i，那么现在要从其它堆取 00 放到第 ii 堆，此时需要操 ci−aic_i-a_i 次。

11 的移动次数

如果 bi>dib_i>d_i，那么现在要把多余的 11 放到其他堆去，但是要先把上方的 00 移到堆的中间，所以要先操作 aa 次（此时不需要除以 22，因为这次操作发生在同一堆内，所以不会被重复计算），再操作 bi−dib_i-d_i 次。
如果 bi<dib_i<d_i，那么现在只要从其它堆取 11 放到第 ii 堆即可，此时需要操作 d−bid-b_i 次。

注意事项

  • 注意由于每次操作会在不同的两个堆内被算，所以最后的结果需要除以 22，才是最终的答案。
  • 多测不清空，爆零两行泪。
  • 十年 OI 一场空，不开 long long 见祖宗。

关键代码

CPP
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;

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...