AcWing 4655. 重新排序
原题链接
中等
作者:
CqAq
,
2024-04-09 00:20:59
,
所有人可见
,
阅读 2
算法1
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
using ll = long long;
const int N = 1E5 + 9;
int n, m;
ll a[N], s[N];
void solve(){
int l, r;
for(int i = 1; i <= m; ++ i){
cin >> l >> r;
s[l] += 1, s[r + 1] -= 1;//记录每一段区间需要加的操作次数
} //根据题意要记录最后的和,每一个点区间要加几次
for(int i = 1; i <=n; ++ i) s[i] += s[i - 1];
ll ans1 = 0;
for(int i = 1; i <= n; ++ i) ans1 += s[i] * a[i];
sort(s + 1, s + 1 + n);
sort(a + 1, a + 1 + n);
ll ans2 = 0;
for(int i = 1; i <= n ; ++ i) ans2 += s[i] * a[i];
cout << ans2 - ans1 << '\n';
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin >> n;
for(int i = 1; i <= n; ++ i) cin >> a[i];
cin >> m;
solve();
return 0;
}