Train Hard, Win Easy 题解(sort)

题目链接

题目大意

题目意思真的有点难懂

总共有个人

就是每个人都会与其余个人进行两两配对

每个人都有自己的两个权值

若配对则每个人的权值加

而有个不能配对两两的关系

求每个人最后的权值

题目思路

其实很简单就是sort一下

然后不能配对的久直接减去即可

代码

#include<bits/stdc++.h>
#define fi first
#define se second
#define debug cout<<"I AM HERE"<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn=3e5+5,inf=0x3f3f3f3f;
const int eps=1e-3;
const ll mod=1004535809;
int n,m;
ll ans[maxn];
ll pre[maxn][3];
int begx[maxn],begy[maxn];
struct node{
    int x,y,id;
}nd[maxn];
bool cmp(node a,node b){
    return a.x+b.y<a.y+b.x;
}
signed main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&nd[i].x,&nd[i].y);
        nd[i].id=i;
        begx[i]=nd[i].x;
        begy[i]=nd[i].y;
    }
    sort(nd+1,nd+1+n,cmp);
    for(int i=1;i<=n;i++){
        pre[i][1]=pre[i-1][1]+nd[i].x;
        pre[i][2]=pre[i-1][2]+nd[i].y;
    }
    for(ll i=1;i<=n;i++){
        ans[nd[i].id]=pre[i-1][1]+(i-1)*nd[i].y+(n-i)*nd[i].x+pre[n][2]-pre[i][2];
        // [1,i-1]
        // [i+1,n]
    }
    for(int i=1,x,y;i<=m;i++){
        scanf("%d%d",&x,&y);
        ans[x]-=min(begx[x]+begy[y],begx[y]+begy[x]);
        ans[y]-=min(begx[x]+begy[y],begx[y]+begy[x]);
    }
    for(int i=1;i<=n;i++){
        printf("%lld ",ans[i]);
    }
    return 0;
}