CF1678A Tokitsukaze and All Zero Sequence 題解

ShanCreeperPro · 2022-05-13 21:24:19 · 题解

CF1678A Tokitsukaze and All Zero Sequence 題解

题面翻译：

给定 t 次询问，每一次输入 n 和 n 个数字 a_i，可以对序列 a 进行以下操作：

• 如果 a_i=a_j，将其中一个数变为 0；
• 否则，将其中一个数变为 \min(a_i,a_j)。

输出将数列全部变为 0 的最小操作次数。

可以证明一定有解。

大胆猜测，最后所需要的操作次数是：

• 如果数列中没有出现 a_i=a_j 且数列中没有 0 的情况，则：

• 如果数列中有 0，则：

• 如果数列中出现 a_i=a_j，则：

接下来，就是对这个贪心思想的证明：

首先，我们需要将数列中的数至少有 2 个数是相同的，所以我们可以将数列 a 排序后判断：

• 如果 a_1=a_2，则不需要进行第二次操作；
• 如果 a_1 \neq a_2，则将 a_1 和 a_2 进行第二次操作，将 a_1 变为 a_2，此时 a_1=a_2。

上述操作需要的步骤数为 1 或 0。

然后，将每个数字变为 0，将 a_1 和 a_2 进行第一次操作，将一个数字变为 0。

接着，将 a_1 和 a_2 进行第二次操作，因为 \min(a_1,a_2)=0，所以 2 个数字都为 0。

然后从 a_2 开始，设此时进行到第 i 为，则：

• 将 a_i 和 a_{i+1} 进行第二次操作，因为 a_i 已经为 0 ，又因为数据范围中 0 \leq a_i，所以不会出现比 0 小的数字：
  • 如果 a_{i+1}=0，则需要跳过；
  • 否则，将 a_{i+1} 变为 0。