写在前面

这道周赛题卡了我一个小时，不管怎么改都是最多过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)，是符合题目的要求的，就是数学计算多了一点。
如果文章有写的不正确的地方还请指出，感恩相遇~