LeetCode C++ 1589. Maximum Sum Obtained of Any Permutation【差分/前缀和/贪心/排序】中等
发布日期:2021-07-01 02:51:50
浏览次数:2
分类:技术文章
本文共 1853 字,大约阅读时间需要 6 分钟。
有一个整数数组 nums
,和一个查询数组 requests
,其中 requests[i] = [starti, endi]
。第 i
个查询求 nums[starti] + nums[starti + 1] + … + nums[endi - 1] + nums[endi]
的结果 ,starti
和 endi
数组索引都是 从 0
开始 的。
你可以任意排列 nums
中的数字,请你返回所有查询结果之和的最大值。由于答案可能会很大,请你将它对 109 + 7
取余 后返回。
示例 1:
输入:nums = [1,2,3,4,5], requests = [[1,3],[0,1]]输出:19解释:一个可行的 nums 排列为 [2,1,3,4,5],并有如下结果:requests[0] -> nums[1] + nums[2] + nums[3] = 1 + 3 + 4 = 8requests[1] -> nums[0] + nums[1] = 2 + 1 = 3总和为:8 + 3 = 11。一个总和更大的排列为 [3,5,4,2,1],并有如下结果:requests[0] -> nums[1] + nums[2] + nums[3] = 5 + 4 + 2 = 11requests[1] -> nums[0] + nums[1] = 3 + 5 = 8总和为: 11 + 8 = 19,这个方案是所有排列中查询之和最大的结果。
示例 2:
输入:nums = [1,2,3,4,5,6], requests = [[0,1]]输出:11解释:一个总和最大的排列为 [6,5,4,3,2,1] ,查询和为 [11]。
示例 3:
输入:nums = [1,2,3,4,5,10], requests = [[0,2],[1,3],[1,1]]输出:47解释:一个和最大的排列为 [4,10,5,3,2,1] ,查询结果分别为 [19,18,10]。
提示:
n == nums.length
1 <= n <= 105
0 <= nums[i] <= 105
1 <= requests.length <= 105
requests[i].length == 2
0 <= starti <= endi < n
题意:重新排列数组,得到所有查询结果之和的最大值。
解法 差分+前缀和+贪心+排序
这一道题不太好想,不过仔细思考可知,如果我们把所有查询区间进行统计,就可以得到每个位置出现的次数。 只要我们把出现次数最多的位置分配给最大的数,次多的位置分配给次大的数……就可以得到所有查询结果之和的最大值。也就是依次将由大到小的数值分给由大到小的出现次数。例如:
输入:nums = [1,2,3,4,5], requests = [[1,3],[0,1]]位置 出现次数0 11 22 13 1于是将位置1分配给数组中最大的数字5, 位置0、2、3依次分配给数组中的数字4、3、2, 位置5分配给1得到: [4,5,3,2,1], 所有查询结果之和为: 4*1 + 5*2 + 3*1 + 2*1 = 19
代码如下,注意:查询数组长度可能有 1 0 5 10^5 105 ,每个查询区间的范围也可能很大,为此使用差分+前缀和进行统计。
#define LL long longconst int MAXN = 1e5 + 10;const int MOD = 1e9 + 7;int cnt[MAXN];class Solution { public: int maxSumRangeQuery(vector & nums, vector>& requests) { int n = nums.size(); for (int i = 0; i <= n; ++i) cnt[i] = 0; //cnt清空 for (const vector & r : requests) { //0<=r[0]<=r[1]
效率如下:
执行用时:912 ms, 在所有 C++ 提交中击败了100.00% 的用户内存消耗:93.7 MB, 在所有 C++ 提交中击败了100.00% 的用户
转载地址:https://memcpy0.blog.csdn.net/article/details/108711074 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
初次前来,多多关照!
[***.217.46.12]2024年04月11日 15时01分08秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
ACM 2013 长沙区域赛 Collision (几何)
2019-04-30
ACM 2014 鞍山区域赛 E - Hatsune Miku (dp)
2019-04-30
反向传播&梯度下降 的直观理解程序(numpy)
2019-04-30
ACM 2017 北京区域赛 J-Pangu and Stones(区间dp)
2019-04-30
java常用类 String面试题
2019-04-30
四线触摸屏原理
2019-04-30
C/C++如何返回一个数组/指针
2019-04-30
腾讯AI语音识别API踩坑记录
2019-04-30
@FeignClient注解的重复名称解决
2019-05-01
java.net.BindException: 无法指定被请求的地址
2019-05-01
scala list
2019-05-01
svn服务器安装
2019-05-01
spark 笔记1
2019-05-01
shell dirname basename
2019-05-01
未来已至,5G加持下的云游戏将走向何方?
2019-05-01
计算机网络 —— 网络层 1.
2019-05-01
Android 之 ContentProvider 与 ContentResolver
2019-05-01
【接口自动化】
2019-05-01
推荐一位川大零基础转行 Python 的人生勇士
2019-05-01
Python解惑之:True与False
2019-05-01