题解 【AT2342 [AGC011F] Train Service Planning】

**题意** ： 有一条铁路，被 $n+1$ 个站台分为 $n$ 段。站台标号为 $0\sim n$ ，铁路标号为 $1\sim n$。 列车通过第 $i$ 段所需时间为 $t_i$ ，可能是双向的或单向的。 现在需要设计一张列车（循环）时刻表。 对于所有的列车，要么从站台 $0$ 前往站台 $n$ ，要么从站台 $n$ 前往站台 $0$ 。 在单向轨道内，不能有两辆相反方向的车互相穿过。列车只能在站点停车等待。 若有一辆开往 $n$ 的车在时刻 $s$ 到达站点 $i$ ，在时刻 $t$ 离开站点 $i$ ，则下一辆车恰好在时刻 $s+k$ 到达站点 $i$ ，在时刻 $t+k$ 离开站点 $i$ 。其中 $k$ 是给定常数。 需要使得时间表中 $0\rightarrow n$ 与 $n\rightarrow 0$ 的列车的所需时间和最短。回答这个最小值，或指出无解。 $n\leq 10^5$ ，时限$\texttt{2s}$。 ------------ 应用题啊…… 当某个 $2t_i>k$ 则无解，否则必定有解。 记 $p_i$ 表示 $0\rightarrow n$ 的车在站点 $i$ 停靠等待的时间。 $q_i$ 表示 $n\rightarrow 0$ 的车在站点 $i$ 停靠等待的时间。 $St(i)=\sum_{j=1}^it_j,\quad Sp(i)=\sum_{j=0}^{i-1}p_j,\quad Sq(i)=\sum_{j=0}^{i-1}q_j$。 某个方向的车经过第 $i$ 段铁路的时间为一段区间，且每 $k$ 单位时间重复一次。 具体地，在模 $k$ 循环意义下 ： 上行车的区间为 $\big(St(i-1)+Sp(i),St(i)+Sp(i)\big)$ 下行车的区间为 $\big(-St(i)-Sq(i),-St(i-1)-Sq(i)\big)$ 实际上下行车的式子是全体减去前缀得到后缀，但是走一整次所需的时间是 $k$ 的倍数，所以在模 $k$ 意义下可以忽略。这样形式上会更统一。 若这是单向铁路，要求两个区间（在模 $k$ 意义下）不交。 $$\left\{ \begin{aligned} St(i-1)+Sp(i)+ck&\notin \big(-St(i)-Sq(i),-St(i-1)-Sq(i)\big)\\ St(i)+Sp(i)+ck&\notin \big(-St(i)-Sq(i),-St(i-1)-Sq(i)\big)\\ -St(i)-Sq(i)+ck&\notin \big(St(i-1)+Sp(i),St(i)+Sp(i)\big)\\ -St(i-1)-Sq(i)+ck&\notin \big(St(i-1)+Sp(i),St(i)+Sp(i)\big) \end{aligned} \right.$$ $$\left\{ \begin{aligned} Sp(i)+Sq(i)+ck&\notin \big(-St(i)-St(i-1),-2St(i-1)\big)\\ Sp(i)+Sq(i)+ck&\notin \big(-2St(i),-St(i)-St(i-1)\big)\\ -Sp(i)-Sp(i)+ck&\notin \big(St(i-1)+St(i),2St(i)\big)\\ -Sp(i)-Sq(i)+ck&\notin \big(2St(i-1),St(i)+St(i-1)\big) \end{aligned} \right.$$ 记 $x_i=Sp(i)+Sq(i)$ ，上式可以统一为 ： $$x_i+ck\notin \big(-2St(i-1),-2St(i)\big)$$ 对 $x_{0\sim n}$ 的唯一约束是 ： 单调不减。 - 于是问题可以转化为 ： 你有一个变量 $x$ ，初始值任意。 每次会给出一个模 $k$ 意义下的区间，要求给 $x$ 加一定值，使得 $x$ 落在这个区间内。 最小化加上的值的和。 （在本题中，还需加上 $2St(n)$ 才是答案） 考虑 $\rm DP$。记 $dp_k[i]$ 为第 $k$ 次操作后使得 $x=i$ 所需的最小代价。 显然我们需要关心的 $i$ 一定为给出的某个端点。 边界 ： $dp_0[i]=0$。 每次操作时，设给出的模意义区间为 $[l,r]$ ，让 $[l,r]$ 以外的位置转移到 $l$ 上，然后将它们置为 $\inf$ ，其余不变。 维护 $dp_k[i]-i$ 的区间 $\min$ 即可。 复杂度 $O(n\log n)$。 ```cpp #include<algorithm> #include<cstdio> #define ll long long #define MaxN 100500 using namespace std; const ll INF=1ll<<60; ll x[MaxN<<1];int tn; struct Node{ ll x;bool fl; inline void ladd(){x=INF;fl=1;} }a[MaxN<<2]; inline void up(int u) {a[u].x=min(a[u<<1].x,a[u<<1|1].x);} void build(int l=1,int r=tn,int u=1) { if (l==r){a[u].x=-x[l];return ;} int mid=(l+r)>>1; build(l,mid,u<<1); build(mid+1,r,u<<1|1); up(u); } inline void ladd(int u){ if (a[u].fl){ a[u<<1].ladd(); a[u<<1|1].ladd(); a[u].fl=0; } } int to,wfl,wfr;ll wfc,ret; void qry(int l=1,int r=tn,int u=1) { if (wfl<=l&&r<=wfr){ ret=min(ret,a[u].x); return ; }int mid=(l+r)>>1;ladd(u); if (wfl<=mid)qry(l,mid,u<<1); if (mid<wfr)qry(mid+1,r,u<<1|1); } void clr(int l=1,int r=tn,int u=1) { if (wfl<=l&&r<=wfr){a[u].ladd();return ;} int mid=(l+r)>>1;ladd(u); if (wfl<=mid)clr(l,mid,u<<1); if (mid<wfr)clr(mid+1,r,u<<1|1); up(u); } void chg(int l=1,int r=tn,int u=1) { if (l==r){ a[u].x=min(a[u].x,wfc-x[l]); return ; }int mid=(l+r)>>1;ladd(u); if (to<=mid)chg(l,mid,u<<1); else chg(mid+1,r,u<<1|1); up(u); } ll dfs(int l=1,int r=tn,int u=1) { if (l==r)return a[u].x+x[l]; int mid=(l+r)>>1;ladd(u); return min(dfs(mid+1,r,u<<1|1),dfs(l,mid,u<<1)); } int n,m,k; ll t[MaxN]; struct Data{ll l,r;}b[MaxN]; int main() { scanf("%d%d",&n,&k); for (int i=1,op;i<=n;i++){ scanf("%lld%d",&t[i],&op); if (op==1&&2*t[i]>k){puts("-1");return 0;} t[i]+=t[i-1]; if (op==1) b[++m]=(Data){(k-2*t[i-1]%k)%k,(k-2*t[i]%k)%k}; } for (int i=1;i<=m;i++){ x[++tn]=b[i].l; x[++tn]=b[i].r; }x[++tn]=0; sort(x+1,x+tn+1); tn=unique(x+1,x+tn+1)-x-1; build(); for (int i=1;i<=m;i++){ int tl=lower_bound(x+1,x+tn+1,b[i].l)-x, tr=lower_bound(x+1,x+tn+1,b[i].r)-x; wfc=INF; if (tl<=tr){ wfl=1;wfr=tl-1; if (wfl<=wfr){ ret=INF;qry();clr(); wfc=b[i].l+ret; } wfl=tr+1;wfr=tn; if (wfl<=wfr){ ret=INF;qry();clr(); wfc=min(wfc,b[i].l+k+ret); } }else { wfl=tr+1;wfr=tl-1; if (wfl<=wfr){ ret=INF;qry();clr(); wfc=b[i].l+ret; } }to=tl;chg(); }printf("%lld",2*t[n]+dfs()); return 0; } ```