AcWing 4655. 重新排序
原题链接
中等
作者:
我是java同学
,
2023-01-09 21:27:36
,
所有人可见
,
阅读 119
思路
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010;
int n, m;
int s[N], w[N];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++)
scanf("%d", &w[i]);
scanf("%d", &m);
while (m --)
{
int l, r;
scanf("%d%d", &l, &r);
s[l] ++, s[r + 1] --;
}
for (int i = 1; i <= n; i ++)
s[i] += s[i - 1];
LL res1 = 0;
for (int i = 1; i <= n; i ++)
res1 += (LL)s[i] * w[i];
LL res2 = 0;
sort(w + 1, w + n + 1);
sort(s + 1, s + n + 1);
for (int i = 1; i <= n; i ++)
res2 += (LL)s[i] * w[i];
printf("%lld\n", res2 - res1);
return 0;
}