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

2023每日刷题（五）

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

向上取整思想

参考了这篇文章

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

$数学式：\frac{x}{y}$有以下两种情况

• x能整除y，则$\frac{x}{y}$就是向上取整和向下取整结果一致的情况，不需要额外转换。也就是说$\frac{x}{y}$的向上取整和向下取整都是它本身，例如$\frac{6}{3}=2$，$\frac{6}{3}$向下取整和向上取整结果都一样，即为2
• x不能整除y，则$\frac{x}{y}$是向下取整结果，不符合我们的需求。例如$\frac{5}{2}=2$,但是我们需要它的向上取整的值，就不能直接用/。

解释一下$(x+y-1)/y$

• 如果x能整除y，那么$(x+y-1)/y$的结果就等价于$x/y$，例如$\frac{6}{3}=2$
• 如果x不能整除y，那么$(x+y-1)/y$结果就是向上取整的值。例如$x=5,y=2$,则$(5+2-1)/2=3$，即为$\frac{5}{2}$向上取整的值。

你也可以这么理解，

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

直接法实现代码

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

测试结果

因为我的时间复杂度太大了，即$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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

测试结果

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