1648-销售价值减少的颜色球-排序+求和

写在前面

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

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 212,686评论 6 492
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 90,668评论 3 385
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 158,160评论 0 348
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 56,736评论 1 284
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 65,847评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,043评论 1 291
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,129评论 3 410
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,872评论 0 268
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,318评论 1 303
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,645评论 2 327
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,777评论 1 341
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,470评论 4 333
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,126评论 3 317
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,861评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,095评论 1 267
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,589评论 2 362
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,687评论 2 351

推荐阅读更多精彩内容

  • 技术交流QQ群:1027579432,欢迎你的加入! 欢迎关注我的微信公众号:CurryCoder的程序人生 1....
    CurryCoder阅读 1,836评论 0 2
  • 前言 2. 实现 Singleton 3. 数组中重复的数字 4. 二维数组中的查找 5. 替换空格 6. 从尾到...
    Observer_____阅读 2,922评论 0 1
  • 排序算法总结 分类编程技术 排序算法平均时间复杂度 冒泡排序O(n2) 选择排序O(n2) 插入排序O(n2) 希...
    Zhs_Android阅读 199评论 0 0
  • 在上一章中,我们介绍了基于单调队列和二进制DP的优化。今天我们来看另外3类,斜率优化,四边形不等式,快速幂优化。 ...
    西部小笼包阅读 2,324评论 4 6
  • 久违的晴天,家长会。 家长大会开好到教室时,离放学已经没多少时间了。班主任说已经安排了三个家长分享经验。 放学铃声...
    飘雪儿5阅读 7,515评论 16 22