专栏文章

CF2122B Pile Shuffling

CF2122B题解参与者 1已保存评论 0

文章操作

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

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

题目传送门

题目大意

nn 个二进制堆,其中第 ii 个堆顶部有 aia_i00bib_i11
每次操作中,你可以取出任意堆的顶部元素,并将其移动到任意堆的任意位置(包括原堆)。
计算最少需要多少次操作,才能使第 ii 个堆形成顶部 cic_i00 和底部 did_i11 的目标状态。

思路

我们需要分别考虑 0011 的数量。

00 的数量

  1. 如果第 ii00 的初始数量大于 00 的目标数量,即 ai>cia_i > c_i,那么现在要把多余的 00 放到其他堆去,此时需要操作 aicia_i - c_i 次。
  2. 如果第 ii00 的初始数量小于 00 的目标数量,即 ai<cia_i < c_i,那么现在要从其它堆取 00 放到第 ii 堆,此时需要操作 ciaic_i - a_i 次。
注意上述操作的操作次数需要除以 22,因为将数字从一个堆放到另一个堆会被计算两次。例如有两个堆,第一个堆有 5500,目标状态为 4400。第二个堆有 3300,目标状态为 4400。此时只需要将第一个堆的一个 00 放在第二个堆即可,只用了一次操作。但要是按照上述操作则需要 22 次操作,所以操作次数要除以 22

11 的数量

  1. 如果第 ii11 的初始数量大于 11 的目标数量,即 bi>dib_i > d_i,那么现在要把多余的 11 放到其他堆去,但是要先把上方的 00 移到堆的中间,所以要先操作 cic_i 次(此时不需要除以 22,因为这次操作发生在同一堆内,所以不会被重复计算),再操作 bidib_i - d_i 次。
  2. 如果第 ii11 的初始数量小于 11 的目标数量,即 bi<dib_i < d_i,那么现在只要从其它堆取 11 放到第 ii 堆即可,此时需要操作 dibid_i - b_i 次。
同理,上述操作的操作次数需要除以 22

关键代码

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

评论

0 条评论,欢迎与作者交流。

正在加载评论...