原文链接: https://leetcode-cn.com/problems/maximum-sum-obtained-of-any-permutation
英文原文
We have an array of integers, nums, and an array of requests where requests[i] = [starti, endi]. The ith request asks for the sum of nums[starti] + nums[starti + 1] + ... + nums[endi - 1] + nums[endi]. Both starti and endi are 0-indexed.
Return the maximum total sum of all requests among all permutations of nums.
Since the answer may be too large, return it modulo 109 + 7.
Example 1:
Input: nums = [1,2,3,4,5], requests = [[1,3],[0,1]] Output: 19 Explanation: One permutation of nums is [2,1,3,4,5] with the following result: requests[0] -> nums[1] + nums[2] + nums[3] = 1 + 3 + 4 = 8 requests[1] -> nums[0] + nums[1] = 2 + 1 = 3 Total sum: 8 + 3 = 11. A permutation with a higher total sum is [3,5,4,2,1] with the following result: requests[0] -> nums[1] + nums[2] + nums[3] = 5 + 4 + 2 = 11 requests[1] -> nums[0] + nums[1] = 3 + 5 = 8 Total sum: 11 + 8 = 19, which is the best that you can do.
Example 2:
Input: nums = [1,2,3,4,5,6], requests = [[0,1]] Output: 11 Explanation: A permutation with the max total sum is [6,5,4,3,2,1] with request sums [11].
Example 3:
Input: nums = [1,2,3,4,5,10], requests = [[0,2],[1,3],[1,1]] Output: 47 Explanation: A permutation with the max total sum is [4,10,5,3,2,1] with request sums [19,18,10].
Constraints:
n == nums.length1 <= n <= 1050 <= nums[i] <= 1051 <= requests.length <= 105requests[i].length == 20 <= starti <= endi < n
中文题目
有一个整数数组 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]。
提示：
n == nums.length1 <= n <= 1050 <= nums[i] <= 1051 <= requests.length <= 105requests[i].length == 20 <= starti <= endi < n
通过代码
高赞题解
解决问题的思路非常简单：我们需要统计每个索引位置的查询次数。然后贪心：越大的数字，分配给查询次数越高的频次。
下面的问题就变成了：如何快速地统计每一个索引的查询次数。
最优方案，也是这个问题实现最简单的方案，就是使用扫描线。即对于每一个request[start, end]，我们知道从 start 开始的数字多了一次查询，从 end + 1 开始的数字少了一次查询。
用一个 freq 数组，对于每一个 request[start, end]，都进行 freq[start] ++ 和 freq[end + 1] -- 操作。
之后，freq[0...i] 的数字和，就是 i 这个索引的查询次数。
我的参考代码（C++）：
class Solution {
private:
const long long MOD = 1e9 + 7;
public:
int maxSumRangeQuery(vector<int>& nums, vector<vector<int>>& requests) {
int n = nums.size();
vector<int> freq(n + 1);
for(const vector<int>& v: requests)
freq[v[0]] ++, freq[v[1] + 1] --;
for(int i = 1; i <= n; i ++)
freq[i] += freq[i - 1];
sort(freq.begin(), freq.begin() + n);
sort(nums.begin(), nums.end());
long long res = 0;
for(int i = n - 1; i >= 0; i --)
res = (res + (long long)nums[i] * freq[i]) % MOD;
return res;
}
};但是，这个问题，因为相当于每个 request，就是在一个区间范围内做 +1 操作，我的第一反应就是线段树。
因为需要区间更新，所以需要懒更新。竞赛选手直接使用模板就好了 >_<
如果有了线段树的代码，主逻辑很直接，如下：
class Solution {
private:
const long long MOD = 1e9 + 7;
public:
int maxSumRangeQuery(vector<int>& nums, vector<vector<int>>& requests) {
int n = nums.size();
SegmentTree tree(n);
for(const vector<int>& v: requests)
tree.add(v[0], v[1]);
vector<int> freq(n);
for(int i = 0; i < n; i ++) freq[i] = tree.query(i);
sort(freq.begin(), freq.end());
sort(nums.begin(), nums.end());
long long res = 0;
for(int i = n - 1; i >= 0; i --)
res = (res + (long long)nums[i] * freq[i]) % MOD;
return res;
}
};针对这个问题，我的包含懒更新的线段树代码如下，有需要的同学可以参考呀：
（不是通用模板，我针对这个问题本身进行了优化，关键是学习懒更新的思路）
class SegmentTree{
private:
int n;
vector<int> tree, lazy;
public:
SegmentTree(int n): n(n), tree(4 * n, 0), lazy(4 * n, 0){}
void add(int uL, int uR){
update(0, 0, n-1, uL, uR);
}
int query(int index){
return query(0, 0, n-1, index);
}
private:
void update(int treeID, int treeL, int treeR, int uL, int uR){
if(lazy[treeID]){
tree[treeID] += (treeR - treeL + 1) * lazy[treeID];
if(treeL != treeR){
lazy[2 * treeID + 1] += lazy[treeID];
lazy[2 * treeID + 2] += lazy[treeID];
}
lazy[treeID] = 0;
}
if (treeL > uR || treeR < uL) return;
if(uL <= treeL && uR >= treeR){
tree[treeID] += treeR - treeL + 1;
if(treeL != treeR){
lazy[2 * treeID + 1] ++;
lazy[2 * treeID + 2] ++;
}
return;
}
int mid = (treeL + treeR) / 2;
update(2 * treeID + 1, treeL, mid, uL, uR);
update(2 * treeID + 2, mid + 1, treeR, uL, uR);
tree[treeID] = tree[treeID * 2 + 1] + tree[treeID * 2 + 2];
return;
}
int query(int treeID, int treeL, int treeR, int index){
if(lazy[treeID]){
tree[treeID] += (treeR - treeL + 1) * lazy[treeID];
if(treeL != treeR){
lazy[2 * treeID + 1] += lazy[treeID];
lazy[2 * treeID + 2] += lazy[treeID];
}
lazy[treeID] = 0;
}
if(treeL== treeR) return tree[treeID];
int mid = (treeL + treeR) / 2;
if(index <= mid) return query(2 * treeID + 1, treeL, mid, index);
return query(2 * treeID + 2, mid + 1, treeR, index);
}
};关于线段树的懒更新，这篇文章可以做入门：https://leetcode.com/articles/a-recursive-approach-to-segment-trees-range-sum-queries-lazy-propagation/
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 4048 | 13713 | 29.5% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
