CF1043E Train Hard, Win Easy 题解

吐槽

这道题难在题意理解有木有。题目倒是不难。

题意搬运

给定 $n$ 个人的两个属性 : $A_i,B_i$ ，并且给出了 $m$ 个关系 :

$x_i$ $y_i$ 表示第 $x_i$ 个人不能和第 $y_i$ 个人配对。

同时 $i,j$ 二人规定配对的价值为 : $A_i + B_j$ 和 $B_i + A_j$ 中的最小值。

现在你需要回答出每个人跟所有人配对（除开不能和自己匹配的人）的价值总和。

解题思路

那么考虑下面式子什么时候成立:

$A_i + B_j < B_i + A_j$

那么我们就得到:

$B_j - A_j < B_i - A_i$

这说明当 $B_j - A_j < B_i - A_i$ 的时候我们应该用 $A_i$ 去匹配 $B_j$ 会得到最小价值。

否则的话我们就应该用 $B_i$ 匹配 $A_j$ 。

所以按照 $B - A$ 从小到大排序，然后再使用前缀和优化即可，详见代码。

Code

有注释

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e5 + 50;
#define int long long
int n,m;
int start[MAXN],tot = 0;
int sum2[MAXN],sum[MAXN],Ans[MAXN],mp[MAXN];

inline int read() {
    int x = 0 , flag = 1;
    char ch = getchar();
    for( ; ch > '9' || ch < '0' ; ch = getchar()) if(ch == '-') flag = -1;
    for( ; ch >= '0' && ch <= '9' ; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
    return x * flag;
}

struct Node {
    int x,y,id;
} P[MAXN];

struct Edge {
    int next,to;
} edge[MAXN * 2];

void add(int u,int v) {
    edge[++tot].next = start[u];
    edge[tot].to = v;
    start[u] = tot;
    return ;
}

bool cmp(Node A, Node B) {
    return (A.y - A.x) < (B.y - B.x);
}

signed main() {
    n = read() , m = read();
    for(int i = 1 ; i <= n ; i ++) P[i].x = read() , P[i].y = read() , P[i].id = i;
    for(int i = 1 ; i <= m ; i ++) {
        int u = read() , v = read();
        add(u, v); add(v, u);
    }
    sort(P + 1 ,  P + 1 + n , cmp);
    for(int i = 1 ; i <= n ; i ++) sum[i] = sum[i - 1] + P[i].y;
        //上面这个就前缀和处理出了 Bj-Aj < Bi - Ai 的所有人的 B 之和
    for(int i = n ; i >= 1 ; i --) sum2[i] = sum2[i + 1] + P[i].x;
        //上面这个就前缀和处理出了 Bj-Aj > Bi - Ai 的所有人的 A 之和
    for(int i = 1 ; i <= n ; i ++) mp[P[i].id] = i;
    for(int i = 1 ; i <= n ; i ++) { //划重点，这个是计算答案的地方
        Ans[P[i].id] += sum[i - 1] + (i - 1) * P[i].x; 
                // (i - 1) 就是 Bj-Aj < Bi - Ai 的所有人的个数，乘上 P[i].x 就表示用 Bi 去匹配
        Ans[P[i].id] += sum2[i + 1] + (n - i) * P[i].y;
                //这里同理
    }
    for(int j = 1 ; j <= n ; j ++) {
        for(int i = start[j] ; i ; i = edge[i].next) {
            int to = edge[i].to;
            Ans[j] -= min(P[mp[j]].x + P[mp[to]].y , P[mp[j]].y + P[mp[to]].x);//暴力减去就行了
        } 
        cout << Ans[j] << " ";
    }
    return 0;
}