leetcode 3066. 超过阈值的最少操作数 II 中等

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。

一次操作中，你将执行：

• 选择 nums 中最小的两个整数 x 和 y 。
• 将 x 和 y 从 nums 中删除。
• 将 min(x, y) * 2 + max(x, y) 添加到数组中的任意位置。

注意，只有当 nums 至少包含两个元素时，你才可以执行以上操作。

你需要使数组中的所有元素都大于或等于 k ，请你返回需要的 最少 操作次数。

示例 1：

输入：nums = [2,11,10,1,3], k = 10
输出：2
解释：第一次操作中，我们删除元素 1 和 2 ，然后添加 1 * 2 + 2 到 nums 中，nums 变为 [4, 11, 10, 3] 。
第二次操作中，我们删除元素 3 和 4 ，然后添加 3 * 2 + 4 到 nums 中，nums 变为 [10, 11, 10] 。
此时，数组中的所有元素都大于等于 10 ，所以我们停止操作。
使数组中所有元素都大于等于 10 需要的最少操作次数为 2 。

示例 2：

输入：nums = [1,1,2,4,9], k = 20
输出：4
解释：第一次操作后，nums 变为 [2, 4, 9, 3] 。
第二次操作后，nums 变为 [7, 4, 9] 。
第三次操作后，nums 变为 [15, 9] 。
第四次操作后，nums 变为 [33] 。
此时，数组中的所有元素都大于等于 20 ，所以我们停止操作。
使数组中所有元素都大于等于 20 需要的最少操作次数为 4 。

提示：

• 2 <= nums.length <= 2 * 10^5
• 1 <= nums[i] <= 10^9
• 1 <= k <= 10^9
• 输入保证答案一定存在，也就是说一定存在一个操作序列使数组中所有元素都大于等于 k 。

分析：每次都要取最小的两个数，并添加一个经过运算的数，可以想到用最小堆来存储这个数组中的数字。建堆时，先记录有多少个数字小于k。每次完成运算时，k的值要减去2.如果得到的新元素仍然小于k，则k加1，这样一直计算到k为0为止。返回运算次数即可。注意到元素最大值为10的9次方，经过运算后有可能会超过int范围，因此用long long存储。

void updata_min_heap(long long *temp,int len)//向上调整堆，即插入新的元素
{
    int index=len;
    while(index>1)
    {
        if(temp[index]<temp[index/2])
        {
            long long a=temp[index];
            temp[index]=temp[index/2],temp[index/2]=a,index/=2;
        }
        else return;
    }
    return;
}

void push_heap(long long *temp,long long a,int index)//建堆
{
    temp[index]=a;
    if(index==1)return;
    updata_min_heap(temp,index);
    return;
}

void down_min_heap(long long *temp,int len)//向下调整堆，即删除元素
{
    int index=1;
    while(index<=len)
    {
//        printf("index=%d len=%d\n",index,len);
        if(index*2<=len)
        {
            if(index*2+1<=len)
            {
                if(temp[index]<=temp[index*2]&&temp[index]<=temp[index*2+1])return;
                else if(temp[index*2]<temp[index]&&temp[index*2]<=temp[index*2+1])
                {
                    long long a=temp[index];
                    temp[index]=temp[index*2],temp[index*2]=a,index*=2;
                }
                else if(temp[index*2+1]<temp[index]&&temp[index*2+1]<=temp[index*2])
                {
                    long long a=temp[index];
                    temp[index]=temp[index*2+1],temp[index*2+1]=a,index=index*2+1;
                }
            }
            else
            {
                if(temp[index]<=temp[index*2])return;
                else
                {
                    long long a=temp[index];
                    temp[index]=temp[index*2],temp[index*2]=a,index*=2;
                }
            }
        }
        else return;
    }
    return;
}

long long get_min(long long *temp,int len)//获取当前堆顶元素，即最小值
{
    long long num=temp[1];
    temp[1]=temp[len],len--;
    down_min_heap(temp,len);
    return num;
}

int minOperations(int* nums, int numsSize, int k) {
    long long temp[numsSize+5];
    int cnt=0,ans=0;
    for(int i=0;i<numsSize;++i)//建堆
    {
        if(nums[i]<k)cnt++;
        push_heap(temp,(long long)nums[i],i+1);
    }
/*
    for(int i=1;i<=numsSize;++i)
        printf("%lld ",temp[i]);
    printf("\n");
*/
    int len=numsSize;
    while(cnt>0)//如果还有元素小于k
    {
        long long a=get_min(temp,len--),b=get_min(temp,len--),c=fmin(a,b)*2+fmax(a,b);
//        printf("a=%lld b=%lld c=%lld\n",a,b,c);
        push_heap(temp,c,len+1);len++;ans++;
/*
        printf("a=%lld b=%lld c=%lld len=%d cnt=%d\n",a,b,c,len,cnt);

        for(int i=1;i<=len;++i)
            printf("%lld ",temp[i]);
        printf("\n");
*/
        if(a<k)cnt--;
        if(b<k)cnt--;
        if(c<k)cnt++;
    }

    return ans;
}