pypy3 解法, 执行用时: 375ms, 内存消耗: 38488K, 提交时间: 2021-09-17 20:10:13

n, m = map(int, input().split())
arr = list(map(int, input().split()))
cnt = [0] * n
for _ in range(m):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    cnt[x] += 1
    cnt[y] -= 1
# 贪心, cnt越大则该位置上的数需要越小
data = []
for i in range(n):
    data.append((cnt[i], i))
data.sort(key=lambda s: s[0], reverse=True)
arr.sort()
res = 0
for i in range(n):
    res += arr[i] * data[i][0]
print(res)

C++ 解法, 执行用时: 31ms, 内存消耗: 1272K, 提交时间: 2021-09-18 08:18:25

#include<bits/stdc++.h>
using namespace std;
int n,m,a[100005],c[100005];
int main() {
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",a+i);
	for(int i=1,x,y;i<=m;i++) scanf("%d%d",&x,&y),c[x]++,c[y]--;
	sort(a+1,a+1+n); sort(c+1,c+1+n);
	long long ans=0;
	for(int i=1;i<=n;i++) ans+=1ll*a[i]*c[n-i+1];
	cout<<ans<<endl;
}