AtCoder AGC011F - Train Service Planning

本题的难点在于建立出数学模型。

对于这个问题,乍一看是难以分析的,不妨通过建立几个函数来形象地表达火车的到达:

$a(i)$:上行火车在 $i$ 站的逗留时间;

$b(i)$:下行火车在 $i$ 站的逗留时间;

$t(i)$ :火车从站台 $i$ 到站台 $i + 1$ 的行驶时间。

特别的,$a(0)$ 表示上行火车的出发时间,$b(n)$ 表示下行火车的出发时间。

那么对于上行火车,其到达 $i$ 站的时间区间为:

对于下行火车,由于每隔时间 $k$ 又会有一辆下行火车,顺推所求的后缀和可以在模意义下变成逆推的前缀和,即:

若当前区间是单向区间,则有:

有不等式:

解得:

在模意义下,不妨可以看成是:

$A(i) + B(i)$ 都是前缀和,其和一定递增,问题转化为:每次移动 $x$ 步,要求第 $i$ 次必须落在区间 $[-2T(i - 1), -2T(i)]$ 内,要求 $A(n) + B(n) + 2T(n)$ 最小,等价于移动步数最小。

考虑贪心,每次走左端点,只需要用线段树转移一下要走几步即可。

注意需要从后往前坐:起点是任意的,终点是一定的。

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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <bits/stdc++.h>

#define MAXN 100005
#define ls x << 1
#define rs x << 1 | 1
#define INF 0x3f3f3f3f3f3f3f3f

typedef long long lint;

using namespace std;

int n, m, k;
lint a[MAXN], suma[MAXN], b[MAXN], l[MAXN], r[MAXN], ele[MAXN << 1];
lint f[MAXN << 1];

struct segment {
int l, r, v;
}t[MAXN << 3];

int read() {
char c = getchar();
int x = 0;
while (!isdigit(c))
c = getchar();
while (isdigit(c)) {
x = (x << 3) + (x << 1) + c - '0';
c = getchar();
}
return x;
}

void build(int l = 1, int r = m, int x = 1) {
t[x].l = l;
t[x].r = r;
t[x].v = 0;
if (l == r)
return ;
int mid = (l + r) >> 1;
build(l, mid, ls);
build(mid + 1, r, rs);
}

void pushdown(int x) {
if (t[x].v) {
t[ls].v = t[rs].v = t[x].v;
t[x].v = 0;
}
}

void modify(int l, int r, int v, int x = 1) {
if (l > r)
return ;
if (l <= t[x].l && t[x].r <= r) {
t[x].v = v;
return ;
}
pushdown(x);
int mid = (t[x].l + t[x].r) >> 1;
if (l <= mid)
modify(l, r, v, ls);
if (r > mid)
modify(l, r, v, rs);
}

int query(int p, int x = 1) {
if (t[x].l == t[x].r)
return t[x].v;
pushdown(x);
int mid = (t[x].l + t[x].r) >> 1;
if (p <= mid)
return query(p, ls);
return query(p, rs);
}

int dis(int x, int y) {
return (ele[y] - ele[x] + k) % k;
}

int main() {
n = read();
k = read();
for (int i = 1; i <= n; ++i) {
a[i] = read();
b[i] = read();
if (b[i] == 1 && a[i] * 2 > k) {
puts("-1");
return 0;
}
suma[i] = suma[i - 1] + a[i];
}
for (int i = 1; i <= n; ++i) {
if (b[i] == 1) {
l[i] = (-suma[i - 1] * 2 % k + k) % k;
r[i] = (-suma[i] * 2 % k + k) % k;
}
else {
l[i] = 0;
r[i] = k - 1;
}
ele[++m] = l[i];
ele[++m] = r[i];
}
sort(ele + 1, ele + m + 1);
m = unique(ele + 1, ele + m + 1) - ele - 1;
build();
for (int i = 1; i <= n; ++i) {
l[i] = lower_bound(ele + 1, ele + m + 1, l[i]) - ele;
r[i] = lower_bound(ele + 1, ele + m + 1, r[i]) - ele;
}
for (int i = n; i >= 1; --i) {
int j = query(l[i]);
if (!j)
f[i] = 0;
else
f[i] = f[j] + dis(l[i], l[j]);
if (l[i] <= r[i]) {
modify(1, l[i] - 1, i);
modify(r[i] + 1, m, i);
}
else
modify(r[i] + 1, l[i] - 1, i);
}
lint ans = f[1];
for (int i = 1; i <= m; ++i) {
int j = query(i);
if (!j)
ans = 0;
ans = min(ans, f[j] + dis(i, l[j]));
}
printf("%lld\n", ans + suma[n] * 2);
}