【题目链接】4655. 重新排序 - AcWing题库
输入样例:
5
1 2 3 4 5
2
1 3
2 5
输出样例:
4
【代码及详细注释】
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
ll a[N],b[N],s[N];
//a用于存储原本的数组
//b用于差分
//s用于存储前缀和求出最开始的和
//贪心思想:让出现次数多的区间点分配到最大的数
int n,m;
void add(int l,int r)
{
b[l]+=1;
b[r+1]-=1;
}
bool cmp(int a,int b)
{
return a>b;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
s[i]=s[i-1]+a[i];
}
cin>>m;
ll ans=0,res=0;//ans用于存储原本的计算结果,res用于计算重新排列后的结果
while(m--)
{
int l,r;
cin>>l>>r;
ans+=s[r]-s[l-1];
add(l,r);//l-r区间上每个数都要出现一次
}
for(int i=1;i<=n;i++)
b[i]+=b[i-1];
sort(b+1,b+1+n,cmp);
sort(a+1,a+1+n,cmp);
int cnt=0;
for(int i=1;i<=n;i++)
{
if(b[i]==0) break;
res+=a[i]*b[i];
}
cout<<res-ans;
return 0;
}