题意
百度翻译党已经阵亡,在网上找到的我觉得比较好的题意,直接搬过来
总共有两道题,给你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; }