思路

对于关系式:

图片说明
xi和yi,都是表示的下标,我们可以先计算下标出现的次数。对下标从大到小排序。大的表示这个数出现的多,我们把ai中的最小数乘以这个次数。
对于小的个数,我们把最小的乘以ai中最大的数,最后求和。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+10;
typedef long long LL;
int a[N],p[N],dex[N];
int cmp(int t1,int t2)
{
    return t1>t2;
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=0; i<n; i++)
        scanf("%d",&a[i]);
    sort(a,a+n);
    memset(p,0,sizeof(p));
    while(m--)
    {
        int t1,t2;
        scanf("%d%d",&t1,&t2);
        p[t1]+=1;
        p[t2]-=1;
    }
    int k=0;
    for(int i=0;i<n;i++)
    {
        if(p[i+1]>0||p[i+1]<0)
            dex[k++]=p[i+1];
    }
    sort(dex,dex+k,cmp);
    /*从大到小,从正数到负数2 1 -1 -2
    k的个数不会超过n*/
    LL sum=0;
    int i;
    for(i=0; i<k&&dex[i]>0; i++)
    {
        sum+=(LL)(dex[i]*a[i]);
    }
    int s=n-1;
   for(int i=k-1;i>=0&&dex[i]<0;i--)
   {
       sum+=(LL)(dex[i]*a[s--]);
   }
    printf("%lld\n",sum);
    return 0;
}