注意事项
1.不能使用暴力计算cnt，否则时间复杂度是O()。
2.注意开long long，否则会爆int。
3.注意数据范围，否则可能会数组越界。
解题思路
1.统计每个元素在查询中的“权重”：
如果一个元素频繁出现在多个查询区间内，那么它的“权重”较高，意味着在最大化总和时，我们应该将该元素设为一个大的数。
2.通过差分数组快速计算权重：
每次查询增加一个区间 到 的和。使用差分数组可以高效地标记每个查询区间的左右边界，得到每个元素被包含的总次数（权重）。
3.重新排列元素使得总和最大化:
将数组 中的数值降序排列，并将权重数组 也降序排列。这样大数与高权重匹配，可以得到最大的和。
AC代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6 + 5;
int a[N] = {}; // 存储原数组 A
ll cnt[N] = {}; // 存储每个位置的权重（出现次数）
ll diff[N] = {}; // 差分数组，帮助快速计算 cnt
int n, m;
int main() {
// 1. 读取输入的 n 和数组 A
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
// 2. 读取查询次数 m 和每个查询的左右端点 L 和 R
cin >> m;
int l, r;
while (m--) {
cin >> l >> r;
diff[l]++; // 差分数组标记左端点
diff[r + 1]--; // 差分数组标记右端点+1
}
// 3. 计算权重数组 cnt（每个元素在所有查询中的出现次数）
for (int i = 1; i <= n; i++) {
cnt[i] = cnt[i - 1] + diff[i];
}
// 4. 计算原数组的总和 sum1
ll sum1 = 0;
for (int i = 1; i <= n; i++) sum1 += a[i] * cnt[i];
// 5. 排序后计算最优结果的总和 sum2
sort(a + 1, a + 1 + n); // 数组 A 排序
sort(cnt + 1, cnt + 1 + n); // 权重数组 cnt 排序
ll sum2 = 0;
for (int i = 1; i <= n; i++) sum2 += a[i] * cnt[i];
// 6. 输出答案，即增量 sum2 - sum1
cout << sum2 - sum1 << endl;
return 0;
}
共 2 条回复
@CPP 偷懒ing
时间复杂度那 O 应为 。个人习惯把所有英文字母与汉字之间打上空格。