网站怎么做排名,网络安全等级保护,网咯鸟深圳网站建设,做外贸的几个网站有一个整数数组 nums #xff0c;和一个查询数组 requests #xff0c;其中 requests[i] [starti, endi] 。第 i 个查询求 nums[starti] nums[starti 1] … nums[endi - 1] nums[endi] 的结果 #xff0c;starti 和 endi 数组索引都是 从 0 开始 的。
你可以任意排列…有一个整数数组 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 8 requests[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 11 requests[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]。 差分
class Solution {
public:int maxSumRangeQuery(vectorint nums, vectorvectorint requests) {int MOD 1e9 7;int n nums.size();vectorint diff(n1);for(auto request: requests){diff[request[0]];diff[request[1]1]--;}int s 0;for(int i 1; i n; i){diff[i] diff[i-1];}std::sort(diff.begin(), diff.end(), greaterint());std::sort(nums.begin(), nums.end(), greaterint());long long res 0;for(int i 0; i n; i){res (long long)nums[i] * diff[i];}return res % MOD;}
};这道题目首先我们可以想到记录request区间覆盖最多次的位置是哪个然后覆盖最多次的位置就将nums最大的值和他相乘然后尽量保证覆盖多次的位置可以乘以较大的值这样最后结果的和才会最大。
我们可以考虑使用差分数组来记录每个位置被覆盖的次数的差分数组然后diff[i] diff[i-1];这个代码遍历diff这时候diff的含义就从差分数组变成了记录每个位置覆盖的次数。由于我们需要找到被覆盖最多的次数然后将次数乘以最大的值被覆盖第二多的次数乘以第二大的值所以我们将diff和nums都进行降序排序。最后将nums[i]*diff[i]相乘记录到res中最后返回的res就是最大的结果
