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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#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;
}
------ 本文结束 ------