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 - 1) / y (x+y−1)/y的结果就等价于 x / y x / y x/y，例如 6 3 = 2 \frac{6}{3}=2 36=2
- 如果x不能整除y，那么 ( x + y − 1 ) / y (x + y - 1) / y (x+y−1)/y结果就是向上取整的值。例如 x = 5 , y = 2 x=5,y=2 x=5,y=2,则 ( 5 + 2 − 1 ) / 2 = 3 (5 + 2 - 1) / 2 = 3 (5+2−1)/2=3，即为 5 2 \frac{5}{2} 25向上取整的值。
你也可以这么理解，
- 若x能整除y，例如x=2y,所以向上整除为2
- 若x不能整除y，例如x=2y+1，也可以是 [ 2 y + 1 , 3 y ) \left[2y+1, 3y\right) [2y+1,3y)，所以 ( x + y − 1 ) / y = ( 2 y + 1 + y − 1 ) = 3 (x + y - 1) / y = (2y + 1 + y - 1) = 3 (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
(
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;
}
文章来源：https://www.toymoban.com/news/detail-722422.html
测试结果
之后我会持续更新，如果喜欢我的文章，请记得一键三连哦，点赞关注收藏，你的每一个赞每一份关注每一次收藏都将是我前进路上的无限动力 ！！！↖(▔▽▔)↗感谢支持！文章来源地址https://www.toymoban.com/news/detail-722422.html
到了这里，关于Leetcode—2530.执行K次操作后的最大分数【中等】(C语言向上取整数学公式)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
