题目描述

难度分:$1500$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。每组数据输入$n(1 \leq n \leq 2 \times 10^5)$，$h(1 \leq h \leq 10^6)$和长为$n$的数组$a(1 \leq a[i] \leq 10^8)$。

一开始你有一个数$sum$，初始值为$h$。每次操作，你可以选择如下三种操作的其中一个：

1. 删除一个小于$sum$的$a[i]$，然后把$sum$增加$\lfloor \frac{a[i]}{2} \rfloor$，其中$\lfloor . \rfloor$表示对$.$向下取整。
2. $sum=sum \times 2$，该操作至多执行$2$次。
3. $sum=sum \times 3$，该操作至多执行$1$次。

输出最多可以删除多少个数。

输入样例

8
4 1
2 1 8 9
3 3
6 2 60
4 5
5 1 100 5
3 2
38 6 3
1 1
12
4 6
12 12 36 100
4 1
2 1 1 15
3 5
15 1 13

输出样例

4
3
3
3
0
4
4
3

算法

贪心+枚举

直觉上肯定是能删数尽量先删数，这样能使$sum$尽可能大。所以先将整个数组排序，然后遍历模拟贪心删数的过程，能删数就直接删数，每当遇到不能删数时有三种贪心顺序：

1. 先将二倍增的操作用完，再用三倍增。
2. 先将三倍增的操作用完，在用两次二倍增。
3. 将三倍增的操作插在两次二倍增之间。

三种策略都尝试一遍，取删数的最大个数作为最终答案。

复杂度分析

时间复杂度

排序一次时间复杂度为$O(nlog_2n)$，三种贪心策略每一种的执行都是线性的时间复杂度$O(n)$。因此算法的瓶颈在于排序，总的时间复杂度为$O(nlog_2n)$。

空间复杂度

除了输入的$a$数组之外，仅使用了有限几个变量，因此算法的额外空间复杂度就是排序的空间复杂度，以快排为基准，额外空间复杂度为$O(log_2n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 200010;
int t, n, h, a[N];

int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d%d", &n, &h);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        sort(a + 1, a + n + 1);
        LL sum = h;
        int ans1 = 0, cnt2 = 0, cnt3 = 0;
        for(int i = 1; i <= n;) {
            if(a[i] < sum) {
                sum += a[i++]/2;
                ans1++;
            }else {
                if(cnt2 < 2) {
                    sum <<= 1;
                    cnt2++;
                }else if(cnt3 < 1) {
                    sum *= 3;
                    cnt3++;
                }else {
                    break;
                }
            }
        }
        int ans2 = 0;
        sum = h;
        cnt2 = cnt3 = 0;
        for(int i = 1; i <= n;) {
            if(a[i] < sum) {
                sum += a[i++]/2;
                ans2++;
            }else {
                if(cnt3 < 1) {
                    sum *= 3;
                    cnt3++;
                }else if(cnt2 < 2) {
                    sum <<= 1;
                    cnt2++;   
                }else {
                    break;
                }
            }
        }
        int ans3 = 0;
        sum = h;
        cnt2 = cnt3 = 0;
        for(int i = 1; i <= n;) {
            if(a[i] < sum) {
                sum += a[i++]/2;
                ans3++;
            }else {
                if(cnt2 == 0) {
                    sum <<= 1;
                    cnt2++;
                }else {
                    if(cnt3 == 0) {
                        sum *= 3;
                        cnt3++;
                    }else {
                        if(cnt2 < 2) {
                            sum <<= 1;
                            cnt2++;
                        }else {
                            break;
                        }
                    }
                }
            }
        }
        printf("%d\n", max(ans1, max(ans2, ans3)));
    }
    return 0;
}