寫在前面

這道周賽題卡了我一個(gè)小時(shí)，不管怎么改都是最多過47個(gè)用例淘钟，我還以為是越界舱卡，結(jié)果是之前模運(yùn)算沒學(xué)好辅肾，真是難受。轮锥。矫钓。

題目

核心思路

別看這題說的很長(zhǎng)，結(jié)合圖示和文字說明舍杜，可以很容易抽象出來：在所給的 inventory 數(shù)組中每次選取一個(gè)最大值inventory[i]新娜，選取的代價(jià)為inventory[i]，按此方法選出 orders 個(gè)數(shù)求和即可既绩。
既然每次都選取最大值概龄，那么很直觀可以想到用一個(gè)大頂堆存儲(chǔ)所有數(shù)據(jù)，然后每次操作在答案中加最大值饲握，然后將堆頂?shù)淖畲笾禍p一私杜，直至取orders次即可蚕键。不過題目給出的orders的最大值可以到 10 ^ 9，采用堆肯定會(huì)超時(shí)了衰粹。
那么有什么優(yōu)化策略呢锣光？因?yàn)轭}目給的總共要取的數(shù)量orders很大，不妨考慮一下是否可以合并操作從而達(dá)到優(yōu)化時(shí)間復(fù)雜度的效果寄猩。既然題目要從最大數(shù)開始取，我們不妨直接給數(shù)組從大到小排序骑疆，參考下邊圖示田篇。

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];
}

這樣得到最后這個(gè)數(shù)finishNum后，就可以分兩部分計(jì)算：

• 對(duì)于一直到下標(biāo) i 之前所有元素充活，使用高斯求和計(jì)算減小到finishNum所得的價(jià)值

finishNum++;//方便計(jì)算蜂莉，這一步在下邊那種情況之后
for (int j = 0; j < i - 1; j++) {
    res = (res + (((long) nums[j] + finishNum) * ((long) nums[j] - finishNum + 1)) / 2) % MOD;
}

• 對(duì)于cnt < orders，要在前i個(gè)數(shù)中依次來取混卵，直到cnt == orders為止
  這一部分我們可以看成一個(gè)整體映穗，那么對(duì)于剩余的操作次數(shù)orders - cnt，可以使得這前i個(gè)數(shù)均減少(orders - cnt) / i幕随；然后蚁滋，再操作剩下的(orders - cnt) % i次，將其中的(orders - cnt) % i個(gè)數(shù)減一即可赘淮，所以可以分成商和余數(shù)分別計(jì)算枢赔，而且都是相同的數(shù)，可以簡(jiǎn)化計(jì)算

int tmp = finishNum;
long times = (orders - cnt) / i;//商拥知，前i個(gè)數(shù)均要減少times
res = (res + ((tmp - times + tmp + 1) * i * (times) / 2)) % MOD;
cnt += times * i;
//余數(shù)為orders - cnt踏拜，表示還需要在前i個(gè)數(shù)中取orders - cnt 個(gè)數(shù)分別減一
res = (res + (((orders - cnt) % MOD) * ((tmp - times) % MOD)) % MOD) % MOD;

將這兩部分的值全都加在一起取模就可以得到最后的答案了。不過要注意計(jì)算求和公式的書寫低剔，由于模運(yùn)算對(duì)除法不支持運(yùn)算速梗，所以涉及/2的部分只能在最后取模肮塞，否則答案會(huì)不正確。

完整代碼

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個(gè)數(shù)均要減少times
        res = (res + ((tmp - times + tmp + 1) * i * (times) / 2)) % MOD;
        cnt += times * i;
        //余數(shù)為orders - cnt枕赵，表示還需要在前i個(gè)數(shù)中取orders - cnt 個(gè)數(shù)分別減一
        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--;
        }
    }
}

雖然沒有使用大佬的二分+貪心，不過只有排序總的時(shí)間復(fù)雜度也是O(NlogN)位隶，是符合題目的要求的拷窜，就是數(shù)學(xué)計(jì)算多了一點(diǎn)。
如果文章有寫的不正確的地方還請(qǐng)指出涧黄，感恩相遇~