概述
G - 风之国
Problem Description
在X轴上有这样一个国家——风之国。风之国虽然是一个国家，但是却有N个首领，每个首领管辖着各自的一个城市。曾几何时，风之国是非常和睦的国家，可是现在突然出现了一个奶茶妹子，各个城市的首领为了这个妹子，掀起了一场没有妹子，就没有夜晚的战争。
这N个城市坐落于X轴上的一些不重复的点上，并且每个城市都只与其左右相邻的城市相互连通。所以一共会有N-1条道路。战争之前任意两个城市之间可以自由贸易。后来因为这场战争，有K对城市由于重要战略物资不允许连通。
X神（掌管X轴的大神）发现了这一点，试图想利用他的法力来破坏一些道路，使得这K对城市两两之间都无法相互连通。
由于破坏每条道路所消耗的法力可能是不一样的，破坏某条道路所消耗的法力是该道路连通的两个城市之间的距离。所以X神想知道最少需要消耗多少的法力，能够使得这K对城市两两之间不能连通。
Input
输入包含多少数据，对于每组数据：
第一行：N K，表示N个城市，K对不允许连通的城市。(2<=N<=100000，0<=K<=100000)。
接下来一行有N个数字x1, x2, x3......xN，其中xi表示第i个城市在X轴上的位置。且每个城市都在不同的位置上。(1<=xi<=10^9, 1<=i<= N)。
接下来K行：u v，表示城市u和城市v不允许连通。输入可能存在重复。(1<=u,v<=n , 且u!=v)
Output
输出一个数，表示X神至少需要消耗多少的法力来破坏一些路，使得这K对城市之间都彼此不连通。
Sample Input
3 3 63 0 132 2 3 1 3 2 1 3 2 63 0 132 2 3 1 2
Sample Output
132 63
Hint
对于第二组数据：
城市2和城市3 不允许连通，
城市1和城市2 不允许连通，
然而对于城市1和城市3没有要求，可连通，可不连通。
G题
时间复杂度：O(N*logN)
方法一：
先对所有点按照x排下序。然后再把k对矛盾点映射为排序后的下标。
然后就是一个dp
Dp[i]表示i前面（包括i）处理掉所有矛盾点的最小花费。
然后状态转移时dp[j] = min( dp[i] + len(i, i + 1) )..
其中a <= i< j。len(i, i + 1)是i与i+1之间的距离， a是j点前面最大的矛盾起点。
求最小值可以用线段树处理。
求出j点dp值之后，把dp[j] + len(j, j + 1)插入到线段树中j位置。
方法二：（YY乱搞版）
同样先对所有点按照x排下序。然后再把这K对矛盾点映射为排序后的下标(u,v)，并使得u<v，然后对这k对矛盾按照右端点v进行从小到大排个序。
然后就是一个乱搞yy的过程。
对于排序后的K对矛盾，按照顺序进行下列步骤：
第一步：求其不允许连通的两个点路径上的最小边，记为Min_E ；
第二步：然后 Ans+=Min_E ；
第三步：再把路径上所有的边的权值都减去最小边的权值。
如此，处理完K对矛盾后，Ans就是答案。
经过我100W的数据对拍，由此得证该方法的正确性！O(∩_∩)O~
|
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
|
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using
namespace
std;
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
const
int
inf = 0x7f7f7f7f;
const
int
maxn = 111111;
inline
int
scanf
(
int
&num)
{
char
in;
bool
neg=
false
;
while
((in=
getchar
())!=EOF && (in>
'9'
|| in<
'0'
) && in!=
'-'
);
if
(in==EOF)
return
0;
else
if
(in==
'-'
) neg=
true
,num=0;
else
num=in-
'0'
;
while
(in=
getchar
(),in>=
'0'
&& in<=
'9'
) num*=10,num+=in-
'0'
;
if
(neg) num=-num;
return
1;
}
struct
SegTree {
int
dp[maxn << 2];
void
build(
int
l,
int
r,
int
rt) {
dp[rt] = inf;
if
(l == r)
return
;
int
m = (l + r) >> 1;
build(lson); build(rson);
}
void
update(
int
x,
int
val,
int
l,
int
r,
int
rt) {
if
(l == r) {
dp[rt] = val;
return
;
}
int
m = (l + r) >> 1;
if
(x <= m) update(x, val, lson);
else
update(x, val, rson);
dp[rt] = min(dp[rt << 1], dp[rt << 1 | 1]);
}
int
query(
int
ll,
int
rr,
int
l,
int
r,
int
rt) {
if
(ll <= l && r <= rr) {
return
dp[rt];
}
int
ret = inf;
int
m = (l + r) >> 1;
if
(ll <= m) ret = min(ret, query(ll, rr, lson));
if
(rr > m) ret = min(ret, query(ll, rr, rson));
return
ret;
}
};
struct
city {
int
idx, x;
inline
void
input(
int
__idx) {
//scanf(x);
scanf
(
"%d"
, &x);
idx = __idx;
}
inline
bool
operator < (
const
city &a)
const
{
return
x < a.x;
}
};
SegTree tree;
int
pre[maxn];
city c[maxn];
int
mp[maxn];
int
n, k;
void
init() {
tree.build(0, n, 1);
memset
(pre, -1,
sizeof
(pre));
}
int
main() {
//freopen("wind.in", "r", stdin);
//freopen("wind.out", "w", stdout);
while
(~
scanf
(
"%d%d"
, &n, &k)) {
init();
for
(
int
i = 1; i <= n; i++) {
c[i].input(i);
}
sort(c + 1, c + n + 1);
for
(
int
i = 1; i <= n; i++) {
mp[ c[i].idx ] = i;
}
for
(
int
i = 1; i <= k; i++) {
int
a, b;
scanf
(
"%d%d"
, &a, &b);
//scanf(a); scanf(b);
a = mp[a]; b = mp[b];
if
(a > b) swap(a, b);
pre[b] = max(pre[b], a);
}
tree.update(0, 0, 0, n, 1);
int
lim = 0;
int
dp;
for
(
int
i = 1; i <= n; i++) {
if
(pre[i] != -1) {
lim = max(pre[i], lim);
}
dp = tree.query(lim, i - 1, 0, n, 1);
tree.update(i, dp + c[i + 1].x - c[i].x, 0, n, 1);
}
printf
(
"%dn"
, dp);
}
}
|
最后
以上就是温暖小蚂蚁为你收集整理的ACdream原创群赛(11)の风神日华神专场 G - 风之国的全部内容，希望文章能够帮你解决ACdream原创群赛(11)の风神日华神专场 G - 风之国所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
![BZOJ 4370: [IOI2015]horses马 线段树+贪心+对数](/uploads/reation/bcimg7.png)
发表评论 取消回复