蓝桥杯备赛-差分-重新排序

问题描述

给定一个数组 AA 和一些查询 Li,RiLi​,Ri​, 求数组中第 LiLi​ 至第 RiRi​ 个元素之和。

小蓝觉得这个问题很无聊, 于是他想重新排列一下数组, 使得最终每个查 询结果的和尽可能地大。小蓝想知道相比原数组, 所有查询结果的总和最多可 以增加多少?

输入格式

输入第一行包含一个整数 nn 。

第二行包含 nn 个整数 A1,A2,⋯,AnA1​,A2​,⋯,An​, 相邻两个整数之间用一个空格分隔。

第三行包含一个整数 mm 表示查询的数目。

接下来 mm 行, 每行包含两个整数 Li、RiLi​、Ri​, 相邻两个整数之间用一个空格分 隔。

输出格式

输出一行包含一个整数表示答案。

样例输入

5
1 2 3 4 5
2
1 3
2 5

样例输出

4

样例说明

原来的和为 6+14=206+14=20, 重新排列为 (1,4,5,2,3)(1,4,5,2,3) 后和为 10+14=2410+14=24, 增 加了 4。

评测用例规模与约定

对于 30%30% 的评测用例， n,m≤50n,m≤50;

对于 50%50% 的评测用例, n,m≤500n,m≤500;

对于 70%70% 的评测用例, n,m≤5000n,m≤5000;

对于所有评测用例, 1≤n,m≤105,1≤Ai≤106,1≤Li≤Ri≤1061≤n,m≤105,1≤Ai​≤106,1≤Li​≤Ri​≤106 。

#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//计算每个位置的查询次数，查询次数最多的放最大的数字
//注意查询和要用long long
//差分--对于一段区间的操作--先在差分数组上做标记--再利用a[i]=a[i-1]+d[i]---重置a数组
//cha是d的前缀和数组，d是cha的差分数组
int main() {int n;cin >> n;vector<int> a(n + 5, 0);vector<int> cha(n + 5, 0);vector<int> d(n + 5, 0);for (int i = 1; i <= n; i++) {cin >> a[i];}//初始化a数组int m;cin >> m;int l, r;for (int i = 1; i <= m; i++) {cin >> l >> r;d[l]++;d[r + 1]--;}//初始化差分数组for (int i = 1; i <= n; i++) {cha[i] = cha[i - 1] + d[i];}//更新cha数组long long sum1 = 0;long long sum2 = 0;for (int i = 1; i <= n; i++){sum1 += (long long)a[i] * cha[i];
//将 sum1 += a[i] * cha[i]; 改为 sum1 += (long long)a[i] * cha[i]; 原因在于数据类型的溢出问题。当 a[i] 和 cha[i] 的值较大时，a[i] * cha[i] 的结果可能会超出 int 类型的表示范围（int 通常是 32 位，范围是 -2^31 到 2^31 - 1）。}sort(a.begin() + 1, a.begin() + 1 + n);//从大到小sort(cha.begin() + 1, cha.begin() + 1 + n);for (int i = 1; i <= n; i++) {sum2 += (long long)a[i] * cha[i];}cout << sum2 - sum1;return 0;
}

 前缀和与差分 图文并茂 超详细整理（全网最通俗易懂）-CSDN博客