写在前面
这道周赛题卡了我一个小时，不管怎么改都是最多过47个用例，我还以为是越界，结果是之前模运算没学好，真是难受。。。
题目
核心思路
别看这题说的很长，结合图示和文字说明，可以很容易抽象出来：在所给的 inventory 数组中每次选取一个最大值inventory[i]，选取的代价为inventory[i]，按此方法选出 orders 个数求和即可。
既然每次都选取最大值，那么很直观可以想到用一个大顶堆存储所有数据，然后每次操作在答案中加最大值，然后将堆顶的最大值减一，直至取orders次即可。不过题目给出的orders的最大值可以到 10 ^ 9，采用堆肯定会超时了。
那么有什么优化策略呢？因为题目给的总共要取的数量orders很大，不妨考虑一下是否可以合并操作从而达到优化时间复杂度的效果。既然题目要从最大数开始取，我们不妨直接给数组从大到小排序，参考下边图示。
可以看到，排序后的数组会从第一个元素开始依次减小，一直减小到图中的
2、1，那么如果我们事先知道最终能减小的数是多少，然后再遍历一遍数组使用高斯求和公式即可算出答案。由于最后的数可能不在数组中，会不好找，而操作20次得到数组全为2，这个2是很容易得到的，所以不妨直接设
finishNum 表示存在于数组中的，满足使数组中最大值变为finishNum的总取数次数小于等于 orders 的最后一个数，这样的话我们一次遍历就可以得到最后这个数
int cnt = 0;
int finishNum = nums[0];
int n = nums.length;
int i = 0;
for (i = 1; i < n; i++) {
int tmp = (nums[i - 1] - nums[i]) * i;
if (cnt + tmp <= orders) {
cnt += tmp;
} else {
break;
}
finishNum = nums[i];
}
这样得到最后这个数finishNum后，就可以分两部分计算：
- 对于一直到下标
i之前所有元素，使用高斯求和计算减小到finishNum所得的价值
finishNum++;//方便计算，这一步在下边那种情况之后
for (int j = 0; j < i - 1; j++) {
res = (res + (((long) nums[j] + finishNum) * ((long) nums[j] - finishNum + 1)) / 2) % MOD;
}
- 对于
cnt < orders，要在前i个数中依次来取，直到cnt == orders为止
这一部分我们可以看成一个整体，那么对于剩余的操作次数orders - cnt，可以使得这前i个数均减少(orders - cnt) / i；然后，再操作剩下的(orders - cnt) % i次，将其中的(orders - cnt) % i个数减一即可，所以可以分成商和余数分别计算，而且都是相同的数，可以简化计算
int tmp = finishNum;
long times = (orders - cnt) / i;//商，前i个数均要减少times
res = (res + ((tmp - times + tmp + 1) * i * (times) / 2)) % MOD;
cnt += times * i;
//余数为orders - cnt，表示还需要在前i个数中取orders - cnt 个数分别减一
res = (res + (((orders - cnt) % MOD) * ((tmp - times) % MOD)) % MOD) % MOD;
将这两部分的值全都加在一起取模就可以得到最后的答案了。不过要注意计算求和公式的书写，由于模运算对除法不支持运算，所以涉及/2的部分只能在最后取模，否则答案会不正确。
完整代码
class Solution {
private static final int MOD = (int) (1e9 + 7);
public int maxProfit(int[] nums, int orders) {
Arrays.sort(nums);
reverse(nums);
long res = 0;
int cnt = 0;
int finishNum = nums[0];
int n = nums.length;
int i = 0;
for (i = 1; i < n; i++) {
int tmp = (nums[i - 1] - nums[i]) * i;
if (cnt + tmp <= orders) {
cnt += tmp;
} else {
break;
}
finishNum = nums[i];
}
int tmp = finishNum;
long times = (orders - cnt) / i;//商，前i个数均要减少times
res = (res + ((tmp - times + tmp + 1) * i * (times) / 2)) % MOD;
cnt += times * i;
//余数为orders - cnt，表示还需要在前i个数中取orders - cnt 个数分别减一
res = (res + (((orders - cnt) % MOD) * ((tmp - times) % MOD)) % MOD) % MOD;
finishNum++;
for (int j = 0; j < i - 1; j++) {
res = (res + (((long) nums[j] + finishNum) * ((long) nums[j] - finishNum + 1)) / 2) % MOD;
}
return (int) res;
}
public void reverse(int[] nums) {
if (nums == null)
return;
int i = 0, j = nums.length - 1;
while (i < j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
i++;
j--;
}
}
}
虽然没有使用大佬的二分+贪心，不过只有排序总的时间复杂度也是O(NlogN)，是符合题目的要求的，就是数学计算多了一点。
如果文章有写的不正确的地方还请指出，感恩相遇~
网友评论