CF2271E.Array Emptying
提高+/省选-
通过率:0%
时间限制:2.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You are given an array a of length n and an integer k.
In one operation, choose any element x of the array.
- If x≤k, erase x from the array.
- Otherwise, erase x and insert two elements equal to ⌈2x⌉.
In both cases, increase k by 1 after performing the operation.
Find the minimum number of operations required to make the array empty.
给你一个长度为 n 的数组 a 和一个整数 k。
在一次操作中,任选数组中的一个元素 x:
- 若 x≤k,则将 x 从数组中删除;
- 否则,将 x 从数组中删除,并插入两个值均为 ⌈2x⌉ 的元素。
在上述两种情况下,执行完该操作后,k 的值均增加 1。
求使数组变为空所需的最少操作次数。
输入格式
Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤104). The description of the test cases follows.
The first line of each test case contains two integers n and k (1≤n≤2⋅105, 0≤k≤n) — the length of the array and the initial value of k.
The second line contains n integers a1,a2,…,an (1≤ai≤n) — the elements of the array.
It is guaranteed that the sum of n over all test cases does not exceed 2⋅105.
每个测试包含多个测试用例。第一行包含测试用例的数量 t(1≤t≤104)。随后是各测试用例的描述。
每个测试用例的第一行包含两个整数 n 和 k(1≤n≤2⋅105,0≤k≤n)——分别表示数组的长度和 k 的初始值。
第二行包含 n 个整数 a1,a2,…,an(1≤ai≤n)——即数组的元素。
保证所有测试用例中 n 的总和不超过 2⋅105。
输出格式
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=0. We can perform the following operations:
- Split an element equal to 4 into two elements equal to 2; k becomes 1.
- Erase an element equal to 1; k becomes 2.
- Erase an element equal to 2; k becomes 3.
- Erase an element equal to 2; k becomes 4.
- Erase an element equal to 4; k becomes 5.
- Erase an element equal to 4; k becomes 6.
The array becomes empty after 6 operations.
In the fourth example, initially k=2. We can perform the following operations:
- Split an element equal to 6 into two elements equal to 3; k becomes 3.
- Erase an element equal to 3; k becomes 4.
- Erase an element equal to 3; k becomes 5.
- Erase an element equal to 5; k becomes 6.
- Erase an element equal to 6; k becomes 7.
- Erase an element equal to 6; k becomes 8.
- Erase an element equal to 6; k becomes 9.
- Erase an element equal to 6; k becomes 10.
The array becomes empty after 8 operations.
在第一个例子中,初始时 k=0。我们可以执行以下操作:
- 将一个值为 4 的元素拆分为两个值为 2 的元素;k 变为 1。
- 删除一个值为 1 的元素;k 变为 2。
- 删除一个值为 2 的元素;k 变为 3。
- 删除一个值为 2 的元素;k 变为 4。
- 删除一个值为 4 的元素;k 变为 5。
- 删除一个值为 4 的元素;k 变为 6。
经过 6 次操作后,数组变为空。
在第四个例子中,初始时 k=2。我们可以执行以下操作:
- 将一个值为 6 的元素拆分为两个值为 3 的元素;k 变为 3。
- 删除一个值为 3 的元素;k 变为 4。
- 删除一个值为 3 的元素;k 变为 5。
- 删除一个值为 5 的元素;k 变为 6。
- 删除一个值为 6 的元素;k 变为 7。
- 删除一个值为 6 的元素;k 变为 8。
- 删除一个值为 6 的元素;k 变为 9。
- 删除一个值为 6 的元素;k 变为 10。
经过 8 次操作后,数组变为空。
输入解题思路,AI测评打分。不知道怎么写?