Leetcode—2530.执行K次操作后的最大分数【中等】(C语言向上取整数学公式)

2023每日刷题（五）

Leetcode—2530.执行K次操作后的最大分数

向上取整思想

参考了这篇文章

有人肯定会问，这个向上取整为什么是这样来的。接下来我简单讲解一下。

数学式：

x

y

数学式：frac{x}{y}

数学式：yx​有以下两种情况

• x能整除y，则

  x

  y

  frac{x}{y}

  yx​就是向上取整和向下取整结果一致的情况，不需要额外转换。也就是说

  x

  y

  frac{x}{y}

  yx​的向上取整和向下取整都是它本身，例如

  6

  3

  =

  2

  frac{6}{3}=2

  36​=2，

  6

  3

  frac{6}{3}

  36​向下取整和向上取整结果都一样，即为2

• x不能整除y，则

  x

  y

  frac{x}{y}

  yx​是向下取整结果，不符合我们的需求。例如

  5

  2

  =

  2

  frac{5}{2}=2

  25​=2,但是我们需要它的向上取整的值，就不能直接用/。

解释一下

(

x

+

y

−

1

)

/

y

(x + y – 1) / y

(x+y−1)/y

• 如果x能整除y，那么$(x+y-1)/y$
• 如果x不能整除y，那么$(x+y-1)/y$

你也可以这么理解，

• 若x能整除y，例如x=2y,所以向上整除为2
• 若x不能整除y，例如x=2y+1，也可以是$\left[2y+1,3y\right)$

直接法实现代码

void max(int *nums, int numsSize, int *e) {
    int i = 0;
    int max = nums[0];
    int cnt = 0;
    for(i = 1; i  numsSize; i++) {
        if(max  nums[i]) {
            max = nums[i];
            cnt = i;
        }
    }
    *e = cnt;
}

long long maxKelements(int* nums, int numsSize, int k){
    int i = 0;
    long long ans = 0;
    int cur = 0;
    for(; i  k; i++) {
        max(nums, numsSize, &cur);
        ans += nums[cur];
        nums[cur] = (nums[cur] + 2) / 3;
    }
    return ans;
}

测试结果

因为我的时间复杂度太大了，即

O

(

k

n

)

O(kn)

O(kn)，主要是也没要求时间复杂度啊。。。接下来用最大堆的方法做，也就是大根堆

最大堆实现代码

void swap(int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

void downAdjustHeap(int* heap, int low, int high) {
    // 相当于双亲为i,左孩子为2*i+1,右孩子为2*i+2,因为这里数组从下标0开始
    int i = low, j = i * 2 + 1;
    while(j  high) {
        if(j + 1  high && heap[j + 1] > heap[j]) {
            j = j + 1;
        }
        if(heap[j] > heap[i]) {
            swap(&heap[j], &heap[i]);
            i = j;
            j = j * 2 + 1;
        } else {
            break;
        }
    }
}

void createHeap(int* arr, int n) {
    // 建立大顶堆
    int i;
    for(i = n / 2 - 1; i >= 0; i--) {
        downAdjustHeap(arr, i, n - 1);
    }
}

long long maxKelements(int* nums, int numsSize, int k){
    // 建立大顶堆,即最大堆
    createHeap(nums, numsSize);
    long long ans = 0;
    int i;
    for(i = 0; i  k; i++) {
        ans += nums[0];
        // 向上取整
        nums[0] = (nums[0] + 2) / 3;
        downAdjustHeap(nums, 0, numsSize - 1);
    }
    return ans;
}

测试结果

之后我会持续更新，如果喜欢我的文章，请记得一键三连哦，点赞关注收藏，你的每一个赞每一份关注每一次收藏都将是我前进路上的无限动力 ！！！↖(▔▽▔)↗感谢支持！

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net

相关推荐: JMeter：断言之响应断言

一、断言的定义 断言用于验证取样器请求或对应的响应数据是否返回了期望的结果。可以是看成验证测试是否预期的方法。 对于接口测试来说，就是测试Request/Response，断言即可以针对Request进行，也可以针对Response进行。但大服务器托管网部分是…