ETrain Hard, Win Easy

题意

百度翻译党已经阵亡，在网上找到的我觉得比较好的题意，直接搬过来

总共有两道题，给你n个人做每道题目的时间，之后是m个关系，这m对人无法组队，两道题目是两个人组队才能做的，每次组队的时候他都会想让总的时间最少，每个人都会和能组队的人组一次，问你这个人最后的总时间是多久。

分析

两两匹配
代价取
假设
换项
我们按照此规则排序即可，在前面的选x，后面的选y
特殊考虑m个不能匹配的情况

参考代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
struct oppo{
    int x,y,id;
    bool operator<(const oppo b){
        return x-y<b.x-b.y;
    }
}a[1000006];
int ans[1000006];
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",&a[i].x,&a[i].y);
        a[i].id=i;
    }
    for(int i=1;i<=m;i++){
        int s,t;
        scanf("%lld%lld",&s,&t);
        int h=min(a[s].x+a[t].y,a[s].y+a[t].x);
        ans[s]-=h;
        ans[t]-=h;
    }
    sort(a+1,a+n+1);
    int tot=0;
    for(int i=1;i<=n;i++){
        ans[a[i].id]+=tot+a[i].y*(i-1);
        tot+=a[i].x;
    }
    tot=0;
    for(int i=n;i>=1;i--){
        ans[a[i].id]+=tot+a[i].x*(n-i);
        tot+=a[i].y;
    }
    for(int i=1;i<=n;i++)
        cout<<ans[i]<<" ";
    return 0;
}