现有一n 个数的序列,给定一个定值k.每次我们可以选择数列中一个下标为 2 的次幂的元素将其删除出数列(删除后,其后的所有元素会自动前移一格)。 问最少进行多少次操作,能将序列中所有值为k 的元素删除? 输入描述 第一行 两个整数n,k 第二行 n 个整数 输出描述 第一行一个整数,为最少操作次数。 样例输入 5 2 1 2 4 2 5 c++实现
时间: 2024-01-24 12:19:07 浏览: 136
题目分析:
题目明确要求删除所有值为k的元素,那么我们可以考虑先记录下所有值为k的元素的下标,然后再从后往前删。因为每次删掉一个元素会导致后面的元素整体前移,所以从后往前删能够保证元素的相对位置不变。
另外,若要删除下标为 i 的元素,则需要将下标为 2i 的元素加入待删除的序列中。这是因为,下标为 2i 的元素在删除下标为 i 的元素后,会自动前移一格,变成下标为 2i-1 的元素。
算法流程:
- 遍历序列,记录下所有值为k的元素的下标;
- 从后往前遍历序列,依次删除所有值为k的元素,并将它们对应的下标的2倍加入待删除的序列中;
- 若待删除的序列不为空,则继续从后往前遍历序列,删除所有待删除元素,并将它们对应的下标的2倍加入待删除的序列中;
- 重复步骤3,直到待删除的序列为空。
代码实现:
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![7z](https://img-home.csdnimg.cn/images/20210720083312.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)