Codeforces 1043E(排序+数学+贡献)

发表于 | 分类于 | | + s

Codeforces 1043E
题意：给出$n$个二元组$(x_i,y_i)$和一个边集$E$，求$\sum min(x_i+y_j, y_i+x_j)$, 其中$(i, j) \notin E$

拆形如$\sum min(x_i+y_j, y_i+x_j)$的式子，设 $x_i+y_j \leq y_i+x_j$ ，则$x_i-y_i \leq x_j-y_j$，用$xi-yi$排序可以使得当$i \leq j$时$i$贡献$x_i$, $j$贡献$y_j$
现在考虑没有边集的情况：所以我们枚举排序后的每个元素，对于他前面的元素，可以用前缀和算贡献；对于后面的元素，可以用后缀和算贡献。
所以如果有边集，我们可以枚举这个点的边集然后删除这个点对贡献。输出答案即可

知识点：
1、排序来解决一些分类讨论问题($max,min,|x|$)(数学上可能叫分段函数)，用排序谓词来满足单调情况的不等式恒成立($x_i+y_j \leq y_i+x_j$, 用$x_i-y_i$排序当$i \leq j$可以保持这个不等式成立)，要熟悉利用一些公式变形技巧
2、特殊化思想：从简单到复杂情况：没有边集怎么做，有了怎么改
3、当有顺序困难时，可以考虑一个排序消除顺序困难：NOIP2017Day1T3

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#define LL long long
#define db double
#define ms(i, j) memset(i, j, sizeof i)

using namespace std;

namespace flyinthesky {

    const int MAXN = 300000 + 5;

    struct data {
        LL xi, yi, id;
        bool operator < (const data &a) const {return xi - yi < a.xi - a.yi;}
    }p[MAXN];

    int n, m, pos[MAXN];
    LL pre_xi[MAXN], suf_yi[MAXN], ans[MAXN];
    vector<int > G[MAXN];

    void clean() {
        ms(ans, 0);
    }
    int solve() {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; ++i) scanf("%lld%lld", &p[i].xi, &p[i].yi), p[i].id = i;
        for (int u, v, i = 1; i <= m; ++i) scanf("%d%d", &u, &v), G[u].push_back(v), G[v].push_back(u);
        clean();
        sort(p + 1, p + 1 + n);
        //for (int i = 1; i <= n; ++i) cerr << "???" << p[i].id << endl;
        for (int i = 1; i <= n; ++i) pos[p[i].id] = i;
        pre_xi[0] = suf_yi[n + 1] = 0;
        for (int i = 1; i <= n; ++i) pre_xi[i] = pre_xi[i - 1] + p[i].xi;
        for (int i = n; i; --i) suf_yi[i] = suf_yi[i + 1] + p[i].yi;
       // for (int i = 1; i <= n; ++i) cerr << "???" << pre_xi[i] << endl;
        for (int i = 1; i <= n; ++i) {
            int u = p[i].id;
            ans[u]  = pre_xi[i - 1] + (LL)(i - 1) * p[i].yi;
            ans[u] += suf_yi[i + 1] + (LL)(n - i) * p[i].xi;
            for (int j = 0; j < (int)G[u].size(); ++j) {
                int v = G[u][j];
                if (pos[v] < i) {
                    ans[u] -= p[i].yi + p[pos[v]].xi;
                } else ans[u] -= p[i].xi + p[pos[v]].yi;
            }
        }
        for (int i = 1; i <= n; ++i) printf("%lld ", ans[i]);
        return 0;
    }
};
int main() {
    flyinthesky::solve();
    return 0;
}
------ 本文结束 ------