CF2271E.Array Emptying

提高+/省选-

通过率:0%

时间限制:2.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

You are given an array aa of length nn and an integer kk.

In one operation, choose any element xx of the array.

  • If x≤kx \le k, erase xx from the array.
  • Otherwise, erase xx and insert two elements equal to ⌈x2⌉\left\lceil \dfrac{x}{2} \right\rceil.

In both cases, increase kk by 11 after performing the operation.

Find the minimum number of operations required to make the array empty.

给你一个长度为 nn 的数组 aa 和一个整数 kk。

在一次操作中,任选数组中的一个元素 xx:

  • 若 x≤kx \le k,则将 xx 从数组中删除;
  • 否则,将 xx 从数组中删除,并插入两个值均为 ⌈x2⌉\left\lceil \dfrac{x}{2} \right\rceil 的元素。

在上述两种情况下,执行完该操作后,kk 的值均增加 11。

求使数组变为空所需的最少操作次数。

输入格式

Each test contains multiple test cases. The first line contains the number of test cases tt (1≤t≤1041 \le t \le 10^4). The description of the test cases follows.

The first line of each test case contains two integers nn and kk (1≤n≤2⋅1051 \le n \le 2 \cdot 10^5, 0≤k≤n0 \le k \le n) — the length of the array and the initial value of kk.

The second line contains nn integers a1,a2,…,ana_1, a_2, \ldots, a_n (1≤ai≤n1 \le a_i \le n) — the elements of the array.

It is guaranteed that the sum of nn over all test cases does not exceed 2⋅1052 \cdot 10^5.

每个测试包含多个测试用例。第一行包含测试用例的数量 tt(1≤t≤1041 \le t \le 10^4)。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 nn 和 kk(1≤n≤2⋅1051 \le n \le 2 \cdot 10^5,0≤k≤n0 \le k \le n)——分别表示数组的长度和 kk 的初始值。

第二行包含 nn 个整数 a1,a2,…,ana_1, a_2, \ldots, a_n(1≤ai≤n1 \le a_i \le n)——即数组的元素。

保证所有测试用例中 nn 的总和不超过 2⋅1052 \cdot 10^5。

输出格式

For each test case, output a single integer — the minimum number of operations required to make the array empty.

对于每个测试用例,输出一个整数——使数组变为空所需的最少操作次数。

输入输出样例

  • 输入#1

    8
    4 0
    4 4 1 4
    3 0
    3 2 2
    6 3
    6 3 6 4 6 5
    6 2
    6 6 5 6 6 6
    5 0
    3 5 3 1 3
    6 1
    6 4 6 5 4 6
    7 1
    7 2 7 7 3 7 7
    8 0
    8 8 2 8 8 1 8 8

    输出#1

    6
    5
    6
    8
    7
    8
    11
    12

说明/提示

In the first example, initially k=0k = 0. We can perform the following operations:

  1. Split an element equal to 44 into two elements equal to 22; kk becomes 11.
  2. Erase an element equal to 11; kk becomes 22.
  3. Erase an element equal to 22; kk becomes 33.
  4. Erase an element equal to 22; kk becomes 44.
  5. Erase an element equal to 44; kk becomes 55.
  6. Erase an element equal to 44; kk becomes 66.

The array becomes empty after 66 operations.

In the fourth example, initially k=2k = 2. We can perform the following operations:

  1. Split an element equal to 66 into two elements equal to 33; kk becomes 33.
  2. Erase an element equal to 33; kk becomes 44.
  3. Erase an element equal to 33; kk becomes 55.
  4. Erase an element equal to 55; kk becomes 66.
  5. Erase an element equal to 66; kk becomes 77.
  6. Erase an element equal to 66; kk becomes 88.
  7. Erase an element equal to 66; kk becomes 99.
  8. Erase an element equal to 66; kk becomes 1010.

The array becomes empty after 88 operations.

在第一个例子中,初始时 k=0k = 0。我们可以执行以下操作:

  1. 将一个值为 44 的元素拆分为两个值为 22 的元素;kk 变为 11。
  2. 删除一个值为 11 的元素;kk 变为 22。
  3. 删除一个值为 22 的元素;kk 变为 33。
  4. 删除一个值为 22 的元素;kk 变为 44。
  5. 删除一个值为 44 的元素;kk 变为 55。
  6. 删除一个值为 44 的元素;kk 变为 66。

经过 66 次操作后,数组变为空。

在第四个例子中,初始时 k=2k = 2。我们可以执行以下操作:

  1. 将一个值为 66 的元素拆分为两个值为 33 的元素;kk 变为 33。
  2. 删除一个值为 33 的元素;kk 变为 44。
  3. 删除一个值为 33 的元素;kk 变为 55。
  4. 删除一个值为 55 的元素;kk 变为 66。
  5. 删除一个值为 66 的元素;kk 变为 77。
  6. 删除一个值为 66 的元素;kk 变为 88。
  7. 删除一个值为 66 的元素;kk 变为 99。
  8. 删除一个值为 66 的元素;kk 变为 1010。

经过 88 次操作后,数组变为空。

输入解题思路,AI测评打分。不知道怎么写?

首页