题目链接

E. Train Hard, Win Easy

分析

只需要做少量的数学计算就可以得出结果

官方题解

code

#include<bits/stdc++.h> using namespace std; #define MAX_VAL 1004 #define MAX_ARRAY_SIZE 300005 #define ms(x,v) memset((x),(v),sizeof(x)) #define pb push_back #define fi first #define se second #define mp make_pair #define INF 0x3f3f3f3f #define MOD 10000 typedef long long LL;// typedef pair<int,int> Pair; LL x[MAX_ARRAY_SIZE],y[MAX_ARRAY_SIZE]; LL d[MAX_ARRAY_SIZE]; int n,m; std::vector<int> G[MAX_ARRAY_SIZE]; int main (int argc, char const *argv[]) { ios_base::sync_with_stdio(0); cin.tie(0); int n,m; cin >>n >> m; for(int i=0 ; i<n ; ++i){ cin >>x[i] >> y[i]; d[i] = y[i] - x[i]; } for(int i=0 ; i<m ; ++i){ int u,v; cin >>u >> v; u--;v--; G[u].pb(v); G[v].pb(u); } LL sx = accumulate(x,x+n,0LL); // std::cout << "sx = " << sx << '\n'; std::vector<LL> sorted_d(d,d+n); sort(sorted_d.begin(),sorted_d.end()); // std::cout << "sorted d" << '\n'; // for(int i=0 ; i<n ; ++i)std::cout << sorted_d[i] << ' ';std::cout << '\n'; std::vector<LL> pre_d(n+1); for(int i=1 ;i<=n ; ++i)pre_d[i] = pre_d[i-1] + sorted_d[i-1]; // std::cout << "pref d" << '\n'; // for(int i=0 ; i<=n ; ++i)std::cout << pre_d[i] << ' ';std::cout << '\n'; // std::cout << " d" << '\n'; // for(int i=0 ; i<=n ; ++i)std::cout << d[i] << ' ';std::cout << '\n'; for(int i=0 ; i<n ; ++i){ // std::cout <<"i = "<< i << '\n'; LL ans = sx + y[i]*(n-1)- x[i]; // std::cout << ans << '\n'; int pos = lower_bound(sorted_d.begin(),sorted_d.end(), d[i]) - sorted_d.begin(); // std::cout <<"pos = " << pos << '\n'; ans += pre_d[pos] - pos*d[i]; // std::cout << "ans = " << ans << '\n'; for(int u : G[i]){ ans -= x[i] + x[u] + min(d[i],d[u]); } std::cout << ans << ' '; // std::cout << '\n'; } return 0; }