题意:

题意有点难懂,这里解释一下.
题意:给你n组数,每组都可以和其他组配对,然后你只能选这个组的a类,那个组的b类/这个组的b类,那个组的a类.然后要求总和最小,当然还给了m组不能配对的点,然后输出每组配对所获得的值.

思路:

暴力的思路十分简单,就是一一配对,然后一一比较即可.但是这样做的时间复杂度是的,显然是不可行的.
那么我们优化思路,发现每次配对都是选a/b,且选出来最优,那么我们直接sort一下,把选a点更优的点放前面,然后就完成了(因为具有单调性.)然后-那些不能选的点的贡献即可.这样的时间复杂度就是.这里用前缀和记录下a的前缀,后缀和记录下b的后缀即可.

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+5;
struct solve{
    ll a,b,id;
}w[N];
int pos[N];//查询原来的id现在的位子.
bool cmp(solve A,solve B)
{
    return A.a+B.b<B.a+A.b;
}
ll ans[N],pre[N],suf[N];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld%lld",&w[i].a,&w[i].b);
        w[i].id=i;
    }sort(w+1,w+1+n,cmp);
    for(int i=1;i<=n;i++)    pos[w[i].id]=i,pre[i]+=pre[i-1]+w[i].a;
    for(int i=n;i>=1;i--)    suf[i]+=suf[i+1]+w[i].b;
    for(int i=1;i<=n;i++)    ans[w[i].id]=pre[i-1]+1ll*(i-1)*w[i].b+suf[i+1]+1ll*(n-i)*w[i].a;
    for(int i=1;i<=m;i++)
    {
        int u,v;scanf("%d%d",&u,&v);
        if(pos[u]<pos[v])    ans[u]-=(w[pos[u]].a+w[pos[v]].b),ans[v]-=(w[pos[u]].a+w[pos[v]].b);
        else                ans[u]-=(w[pos[u]].b+w[pos[v]].a),ans[v]-=(w[pos[u]].b+w[pos[v]].a);
    }
    for(int i=1;i<=n;i++)    printf("%lld ",ans[i]);
    puts("");
    return 0;
}