CF1043E Train Hard, Win Easy

題意：

n個人有Ai和Bi兩個屬性，給出m個關系：xi yi表示xi和yi不能配對
i,j兩人規定匹配的價值為min (Ai + Bj , Bi + Aj )
回答出每個人跟所有人配對（除開不能和自己匹配的人）的價值總和

題解：

兩兩匹配
取min (Ai + Bj , Bi + Aj )
假設 Ai + Bj < Bi + Aj
Ai - Aj < Bi -Bj
按照此規則排序即可，在前面的選x，后面的選y
再考慮m個不能匹配的情況
具體實現：先減去m個不能匹配的值，然后再加上所有匹配情況的值
對于第i個數，用它的y與前面的x匹配，用它的x與后面的y匹配

代碼：

#include<bits/stdc++.h> #define int long long using namespace std; int n,m; const int maxn=1000006; struct node{int x,y,id;bool operator<(const node b){return x-y<b.x-b.y;} }a[maxn]; int ans[maxn]; int sum[maxn],sum2[maxn]; 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 u,v;scanf("%lld%lld",&u,&v);int h=min(a[u].x+a[v].y,a[u].y+a[v].x);ans[u]-=h;ans[v]-=h;}sort(a+1,a+n+1);int tot=0;for(int i = 1 ; i <= n ; i ++) sum[i] = sum[i - 1] + a[i].x;for(int i = n ; i >= 1 ; i --) sum2[i] = sum2[i + 1] + a[i].y;for(int i = 1 ; i <= n ; i ++) { ans[a[i].id] += sum[i - 1] + (i - 1) * a[i].y;ans[a[i].id] += sum2[i + 1] + (n - i) * a[i].x;}for(int i=1;i<=n;i++)cout<<ans[i]<<" ";return 0; }

總結

以上是生活随笔為你收集整理的CF1043E Train Hard, Win Easy的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。