简要题意
一条铁路被 $n+1$ 个站台分位 $n$ 段. 站台标号为 $0 \sim n$ , 铁路标号为 $1 \sim n$ .
列车通过第 $i$ 段所需时间为 $t_i$ , 铁路可能是允许两辆车相对而行或者是一辆车单行.
现在需要设计一张列车表.
对于所有的车, 要么从 $0$ 站台到 $n$ 站台, 要么从 $n$ 站台到 $0$ 站台.
若一辆开往 $n$ 的车在时刻 $s$ 到达站台 $i$ , 在时刻 $t$ 离开站台 $i$ , 则下一辆开往 $n$ 的车桥恰好在时刻 $s+k$ 到达站台 $i$ , 在时刻 $t+k$ 离开站台 $i$ , 对于开往 $0$ 的车同理, 其中 $k$ 为给定常数.
要使得时间表中 $0 \rightarrow n$ 和 $n \rightarrow 0$ 的列车所需时间和最短.
$n \leqslant 10^5$ .
题解
考虑是每 $k$ 分钟有一辆车, 所以不妨把所有操作都在模 $k$ 意义下进行.
我们称从 $0$ 到 $n$ 的车为上行, 另一种为下行.
令 $p_i$ 为上行车在 $i$ 站台的停留时间, $q_i$ 为下行车在 $i$ 站台的停留时间, $a_i$ 表示第 $i$ 个站台和第 $i+1$ 个站台之间的行驶时间, $S(a,i)$ 为 $a$ 数组的前缀和.
显然如果合法, 双向铁路不用管, 上下行车在某一段单向铁路上行驶的区间肯定不相交.
我们把上下行车在第 $i$ 段铁路上行驶时间区间写出来.
上行: $(S(a,i-1)+S(p,i),S(a,i)+S(p,i))$ .
下行: $(-S(a,i-1)-S(q,i),-S(a,i)-S(q,i))$ .
这里有一个很巧妙的转化, 因为在模 $k$ 意义下运算, 本来应该是两个后缀相加, 但这样两个式子不统一, 所以我们把后缀看成总和减去前缀和, 那么总和可以调整为 $k$ 的倍数, 就没了.
如果两个区间不交, 任意一个区间的端点不会在另一个区间内, 由此可以得到一些不等式, 形式大概为这样:
最终化简, 得到这个结论.
可以看到, 对于每个 $i$ , 它不可选的区间是固定的.
那么我们考虑它在模 $k$ 意义下, 这个区间的补集(对于补集有两段, 相当于平移左边的段到右边), 设它为 $[L_i,R_r]$ .
我们发现, 这题的答案实际上就是最小化 $S(p,n)+S(q,n)+2S(a,n)$ , 等价于最小化 $S(p,n)+S(q,n)$ .
这样, 我们把问题转化为, 给定 $n$ 个区间, 任选起点, 走 $n$ 步, 第 $i$ 步需要落在区间 $i$ 中, 求最小路径总长度.
注意这里的走是在模 $k$ 意义下的.
这样就可以变成一个 $dp$ 问题了.
首先这个问题有一个贪心的结论, 如果起点已经确定了, 那么每次走都走到下个区间的左端的肯定最优.
那么我们可以先预处理出来, 在每个起点出发后, 一直走左端点直到走完, 需要走的最小距离.
定义 $f_i$ 表示对于区间 $[L_i,R_i]$ 的左端点 $L_i$ 而言, 一直走左端点到 $n$ 的最短路径.
那么我们考虑倒着推这个 $dp$ .
每推完一个 $f_i$ 时, 我们就把区间 $[L_i,R_i]$ 的补集在线段树上的值覆盖为 $i$ .
然后推 $f_i$ 时, 每次查询 $L_i$ 位置的线段树上的值, 设这个值时 $j$ .
那么显然, 编号在区间 $[i,j-1]$ 中的所有区间都覆盖了 $L_i$ 这个点.
那么显然编号在 $[i,j-1]$ 中的所有区间都覆盖了 $L_i$ 这个点。
所以直接不动就可以走玩这些区间了.
那么我们用 $f_j+dis(L_i,L_j)$ 来更新 $f_i$ .
再覆盖区间即可.
最后统计答案.
枚举所有出现的 $L_i$ 和 $R_i$ , 并把它们作为起点, 求出答案.
显然如果不选这些点的话答案只会更劣.
代码
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
|
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
#define int ll
typedef pair <int,int> pii;
#define DEBUG(x) cout << #x << " = " << x << "\n"
template <typename T>
inline bool read(T &x) {
int f = 1,c = getchar();x = 0;
while (!isdigit(c)) {if (c == 45)f = -1;c = getchar();}
while (isdigit(c))x = (x<<3)+(x<<1)+(c^48),c = getchar();
return x *= f,true;
}
template <typename T,typename... Args>
inline bool read(T &x,Args &...args) {
return read(x) && read(args...);
}
namespace run {
const int maxn = 2e5+10,maxm = 5e5+10;
int a[maxn],b[maxn],sum[maxn];
int num[maxm],tot;
int tree[maxm],L[maxn],R[maxn],f[maxn];
int n,K,ans;
inline void pushdown(int root) {
if (!tree[root])return;
tree[root<<1] = tree[root<<1|1] = tree[root];
tree[root] = 0;
return;
}
inline void update(int root,int l,int r,int al,int ar,int val) {
if (al > ar)return;
if (l > ar || r < al)return;
if (al <= l && r <= ar)return tree[root] = val,void();
pushdown(root);
int mid = (l+r)>>1;
update(root<<1,l,mid,al,ar,val);
update(root<<1|1,mid+1,r,al,ar,val);
return;
}
inline ll query(int root,int l,int r,int pos) {
if (l == r)return tree[root];
pushdown(root);
int mid = (l+r)>>1;
if (pos <= mid)return query(root<<1,l,mid,pos);
else return query(root<<1|1,mid+1,r,pos);
}
inline ll query(ll pos) {
ll tmp = query(1,1,tot,pos);
if (!tmp)return 0;
return (f[tmp]+(num[L[tmp]]-num[pos]+K)%K);
}
inline bool main() {
read(n,K);
for (int i = 1;i <= n;++i) {
read(a[i],b[i]);
sum[i] = sum[i-1]+a[i];
if (b[i] == 2)continue;
if (2*a[i] > K)return puts("-1")&0;
}
for (int i = n;i >= 1;--i) {
if (b[i] == 1) {
L[i] = (-2ll*sum[i-1]%K+K)%K;
R[i] = (-2ll*sum[i]%K+K)%K;
}
else L[i] = 0,R[i] = K-1;
num[++tot] = L[i],num[++tot] = R[i];
}
sort(num+1,num+1+tot);
tot = unique(num+1,num+1+tot)-num-1;
for (int i = n;i >= 1;--i) {
L[i] = lower_bound(num+1,num+1+tot,L[i])-num;
R[i] = lower_bound(num+1,num+1+tot,R[i])-num;
f[i] = query(L[i]);
if (L[i] > R[i])update(1,1,tot,R[i]+1,L[i]-1,i);
else update(1,1,tot,1,L[i]-1,i),update(1,1,tot,R[i]+1,tot,i);
}
ans = f[1];
for (int i = tot;i >= 1;--i)ans = min(ans,query(i));
printf("%lld\n",ans+sum[n]*2ll);
return 0;
}
}
#undef int
#define demonlover
int main() {
#ifdef demonlover
freopen("AGC11F.in","r",stdin);
freopen("AGC11F.out","w",stdout);
#endif
return run :: main();
}
|