描述
给定一个数组 A 和一些查询 Li,Ri,求数组中第 Li 至第 Ri 个元素之和。
小蓝觉得这个问题很无聊,于是他想重新排列一下数组,使得最终每个查询结果的和尽可能地大。
小蓝想知道相比原数组,所有查询结果的总和最多可以增加多少?
输入
输入第一行包含一个整数 n。
第二行包含 n 个整数 A1,A2,⋅⋅⋅,An相邻两个整数之间用一个空格分隔。
第三行包含一个整数 m 表示查询的数目。
接下来 m 行,每行包含两个整数 Li、Ri相邻两个整数之间用一个空格分隔。
输出
输出一行包含一个整数表示答案。
样例输入
5
1 2 3 4 5
2
1 3
2 5
样例输出
4
提示
样例解释:
原来的和为 6+14=20,重新排列为 (1,4,5,2,3) 后和为 10+14=24,增加了 4。
数据范围
对于 30%的评测用例,n,m≤50;
对于 50%的评测用例,n,m≤500;
对于 70%的评测用例,n,m≤5000;
对于所有评测用例,1≤n,m≤105,1≤Ai≤106,1≤Li≤Ri≤n。
显然贪心思路就是让出现次数越多的位置上的数越大
由于只需要修改不需要查询,因此我们可以通过 一维差分 统计每个位置的次数,对差分做前缀和即可得到每个位置出现次数的数组
原先查询结果的总和 = 每个位置出现次数 * 位置上的数
排列后查询结果的总和 = 每个位置出现次数 * 重新排列后位置上对应的数,由于数的大小与次数成正比,因此只要分别对两个数组排序即可
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e5+10,inf = 0x3f3f3f3f; ll a[N],d[N]; ll n,m; int main() { cin >> n; for(int i=1;i<=n;i++)scanf("%d",&a[i]); cin >> m; while(m--) { int l,r; scanf("%d %d",&l,&r); d[l]++; d[r+1]--; } ll sum1 = 0,sum2 = 0; for(int i=1;i<=n;i++) { d[i]+=d[i-1]; sum1+=a[i]*d[i]; } sort(a+1,a+1+n); sort(d+1,d+1+n); for(int i=1;i<=n;i++) sum2+=a[i]*d[i]; cout << sum2 - sum1; return 0; }
标签:int,ll,整数,查询,差分,数组,8016,排序,Ri From: https://www.cnblogs.com/jyssh/p/17636395.html