做法:前缀和,贪心
思路
由题意可知,我们可以根据排序,即 贪心思想
可以根据前缀和的思想先把每个人与他人的答案求出来(如果不考虑不愿意配对的情况)
设自己排序后的位置为i
前i个选自己的x以及他人的y最优
第i个之后的选自己的y以及他人的x最优然后再减去不愿意配对的情况
考虑他们两个排序后位置的前后情况,是减去谁的x,谁的y
代码
#include <bits/stdc++.h> using namespace std; #define pb push_back #define mp(aa,bb) make_pair(aa,bb) #define _for(i,b) for(int i=(0);i<(b);i++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define per(i,b,a) for(int i=(b);i>=(a);i--) #define mst(abc,bca) memset(abc,bca,sizeof abc) #define X first #define Y second #define lowbit(a) (a&(-a)) #define debug(a) cout<<#a<<":"<<a<<"\n" typedef long long ll; typedef pair<int,int> pii; typedef unsigned long long ull; typedef long double ld; const int N=300010; const int INF=0x3f3f3f3f; const int mod=1e9+7; const double eps=1e-6; const double PI=acos(-1.0); int n,m; struct node{ ll x,y,id; }s[N]; vector<int> g[N]; ll sumx[N],sumy[N]; ll pos[N],ans[N]; bool cmp(node a,node b){ return a.x-a.y<b.x-b.y; } void solve(){ cin>>n>>m; rep(i,1,n){ cin>>s[i].x>>s[i].y; s[i].id=i; } while(m--){ int u,v;cin>>u>>v; g[u].pb(v); g[v].pb(u); } sort(s+1,s+1+n,cmp); rep(i,1,n){ pos[s[i].id]=i; sumx[i]=sumx[i-1]+s[i].x; } per(i,n,1) sumy[i]=sumy[i+1]+s[i].y; rep(i,1,n) ans[s[i].id]=(s[i].y*(i-1)+sumx[i-1])+(s[i].x*(n-i)+sumy[i+1]); for(int i=1;i<=n;i++){ for(int j:g[i]){ if(pos[i]<pos[j]) ans[i]-=s[pos[i]].x+s[pos[j]].y; else ans[i]-=s[pos[i]].y+s[pos[j]].x; } cout<<ans[i]<<" \n"[i==n]; } } int main(){ ios::sync_with_stdio(0);cin.tie(0); // int t;cin>>t;while(t--) solve(); return 0; }