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 = (2 y + 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;
}