题目
思路
对条件进行一下变形
如果对于\(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;
}