leetcode_2233. K 次增加后的最大乘积
题目链接:2233. K 次增加后的最大乘积 - 力扣(LeetCode)
// 小根堆
#define INVALUE ((int)pow(10, 6) + 1)
#define MOD ((int)pow(10, 9) + 7)
static int cmp(const void *a, const void *b)
{
return (*(int*)a - *(int*)b);
}
int maximumProduct(int* nums, int numsSize, int k)
{
long long ans = 1;
int heap[numsSize + 1];
heap[0] = -1;
memcpy(heap + 1, nums, sizeof(int) * numsSize);
qsort(heap, numsSize + 1, sizeof(int), cmp);
while (k--) {
int idx = 1;
heap[idx] += 1;
bool flag = true;
while (flag && (2 * idx <= numsSize)) {
int pos = 2 * idx;
int left = heap[pos];
int right = (pos + 1 <= numsSize ? heap[pos + 1] : INVALUE);
if (left > right) {
++pos;
}
if (heap[idx] > heap[pos]) {
int tmp = heap[idx];
heap[idx] = heap[pos];
heap[pos] = tmp;
idx = pos;
continue;
}
flag = false;
}
}
for (int i = 1; i <= numsSize; i++) {
ans = (ans * heap[i]) % MOD;
}
return ans;
}