Codeforces 854D(前缀和+二分)

Codeforces 854D
题意:有n+1个城市,每个城市都有一个人,他们要去0城市参加活动,一起待k天,然后再回来,你可以提前去也可以延后回去,问 你能不能使所有人一起待k天,可以的话,最小花费是多少?

我们维护两个前缀和数组$l_i, r_i$,分别表示$i$前面的航班可以使得所有人到达0城市的最小费用、$i$后前面的航班可以使得所有人回去的最小费用,计算直接再开个数组记录各个城市的最小值即可。
然后答案可以合并,是$max(l_i+r_j)$,其中$j$是离$d_i+k+1$天最近的航班。
因为有可能回去的$r_i$对应的航班$i$是到达0城市的航班,中途被我continue了(其实其他方法可以避免),使得单调性被破坏,我们可以进行恢复单调性(看代码注释部分),所以直接找 离$d_i+k+1$天最近的航班 就是当前最优解。用二分找较为合适,复杂度$O(nlogn)$

Codeforces Submission

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXM = 100000 + 5;
const LL INF = 9223372036854775807;
struct data {
int d, f, t, c;
bool operator < (const data &b) const {
return d < b.d;
}
}a[MAXM];
int n, m, k;
LL l[MAXM], r[MAXM], cost[MAXM];
void clean() {
for (int i = 0; i <= m + 1; i++) l[i] = r[i] = -1;
}
void solve() {
clean();
for (int i = 1; i <= m; i++) scanf("%d%d%d%d", &a[i].d, &a[i].f, &a[i].t, &a[i].c);
sort(a + 1, a + 1 + m);
for (int i = 0; i <= m + 1; i++) cost[i] = INF;
int cnt = 0;
LL tot = 0;
for (int i = 1; i <= m; i++) {
if (a[i].f == 0) continue;//单调性被破坏,但是这里无所谓,因为都能被遍历到
if (cost[a[i].f] == INF) cnt++, cost[a[i].f] = (LL)a[i].c, tot += (LL)a[i].c; else
if (cost[a[i].f] > a[i].c) tot -= cost[a[i].f], cost[a[i].f] = (LL)a[i].c, tot += (LL)a[i].c;
if (cnt == n) l[i] = tot;
}
for (int i = 0; i <= m + 1; i++) cost[i] = INF;
cnt = 0, tot = 0;
for (int i = m; i >= 1; i--) {
if (a[i].t == 0) continue;//单调性被破坏
if (cost[a[i].t] == INF) cnt++, cost[a[i].t] = (LL)a[i].c, tot += (LL)a[i].c; else
if (cost[a[i].t] > a[i].c) tot -= cost[a[i].t], cost[a[i].t] = (LL)a[i].c, tot += (LL)a[i].c;
if (cnt == n) r[i] = tot;
}
for (int i = m - 1; i >= 1; i--) {//恢复单调性
if (r[i] == -1) r[i] = r[i + 1];
}
LL sc = INF;
for (int i = 1; i <= m; i++) {
int ans = 0, dd = a[i].d + k + 1, L = i + 1, R = m + 1;
if (l[i] == -1) continue;
if (L > R) continue;
while (L < R) {
int mid = (L + R) >> 1;
if (a[mid].d < dd) {
L = mid + 1;
} else ans = R = mid;
}
if (r[ans] == -1) continue;
sc = min(sc, l[i] + r[ans]);
}
if (sc == INF) printf("-1\n"); else printf("%I64d\n", sc);
}
int main() {
scanf("%d%d%d", &n, &m, &k), solve();
return 0;
}

------ 本文结束 ------