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;
}

测试结果

因为我的时间复杂度太大了，即$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;
}

测试结果

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