网站设计论文开题报告,长页在线制作网站,官方网站建设 省心磐石网络,免费网络电话app问题描述
给定一个数组 AA 和一些查询 Li,RiLi,Ri, 求数组中第 LiLi 至第 RiRi 个元素之和。
小蓝觉得这个问题很无聊, 于是他想重新排列一下数组, 使得最终每个查 询结果的和尽可能地大。小蓝想知道相比原数组, 所有查询结果的总和最多可 以增加多少?
输入格式
输…问题描述
给定一个数组 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样例说明
原来的和为 6142061420, 重新排列为 (1,4,5,2,3)(1,4,5,2,3) 后和为 101424101424, 增 加了 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 。
#includestdio.h
#includeiostream
#includevector
#includealgorithm
using namespace std;
//计算每个位置的查询次数查询次数最多的放最大的数字
//注意查询和要用long long
//差分--对于一段区间的操作--先在差分数组上做标记--再利用a[i]a[i-1]d[i]---重置a数组
//cha是d的前缀和数组d是cha的差分数组
int main() {int n;cin n;vectorint a(n 5, 0);vectorint cha(n 5, 0);vectorint 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博客
