题目

传送门

思路

对条件进行一下变形

如果对于\(i，j\)两个人，如果\(i\)选择\(x_i\)，则必定有关系

\(x_i+y_j<y_i+x_j\)

之后移下项

\(x_i-x_j<y_i-y_j\)

之后排序算贡献就可以了

代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define int long long
int n,m;
struct node
{
    int x,y,id;
    int ori;
    long long s;
    friend bool operator < (const node &a,const node &b)
    {
        return a.x-a.y<b.x-b.y;
    }
}a[300005];
long long sx[300005];
long long sy[300005];
bool cmp(node a,node b)
{
    return a.ori<b.ori;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].x>>a[i].y;
        a[i].ori=i;
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)
    {
        a[i].id=i;
        sx[i]=sx[i-1]+a[i].x;
        sy[i]=sy[i-1]+a[i].y;
    }
    for(int i=1;i<=n;i++)
        a[i].s=(i-1)*a[i].y+(n-i)*a[i].x+sx[i-1]+sy[n]-sy[i];
    sort(a+1,a+n+1,cmp);
    for(int i=1,x,y;i<=m;i++)
    {
        cin>>x>>y;
        if(a[x].id<a[y].id)
        {
            a[x].s=a[x].s-a[x].x;
            a[x].s=a[x].s-a[y].y;
            a[y].s=a[y].s-a[x].x;
            a[y].s=a[y].s-a[y].y;
        }
        else    
        {
            a[x].s=a[x].s-a[x].y-a[y].x;
            a[y].s=a[y].s-a[x].y-a[y].x;
        }
    }
    for(int i=1;i<=n;i++)
        cout<<a[i].s<<' ';
    return 0;
}

习题：Train Hard, Win Easy（水题）

原文：https://www.cnblogs.com/loney-s/p/12246250.html