题解：
比较容易想到二分答案+时间逆流
这样就变成了经典的路灯问题 f[a][b][0/1]
其实可以不用二分答案
根据倒着考虑我们会发现一定是先走旁边的再走中间的
计算到当前点+下课时间所需的最小时间
代码：
神奇的wa了一个点 对拍并不能拍出来
#include <bits/stdc++.h> using namespace std; #define rint int #define IL inline #define rep(i,h,t) for (rint i=h;i<=t;i++) #define dep(i,t,h) for (rint i=t;i>=h;i--) #define me(x) memset(x,0,sizeof(x)) #define ll long long const int N=1100; const int INF=1e9; int n,m,k; int f[N],g[N][N][2],maxa,p[N]; IL void minn(rint& x,rint y) { if (x>y) x=y; } struct re{ int a,b; }a[N]; IL bool cmp(re x,re y) { return x.a<y.a; } int main() { freopen("1.in","r",stdin); freopen("1.out","w",stdout); ios::sync_with_stdio(false); cin>>n>>m>>k; int maxa=0; rep(i,1,m) { cin>>a[i].a>>a[i].b; } sort(a+1,a+m+1,cmp); a[0].a=INF; int cnt=0; rep(i,1,m) { if (a[i].a!=a[i-1].a) cnt++; f[cnt]=max(f[cnt],a[i].b); p[cnt]=a[i].a; } maxa=cnt+1; p[maxa]=p[maxa-1]; rep(i,0,N-1) rep(j,0,N-1) g[i][j][0]=g[i][j][1]=INF; g[0][maxa][0]=0; dep(i,maxa,0) rep(j,0,maxa-i) { rint k=j+i; if (g[j][k][0]!=INF) minn(g[j+1][k][0],max(g[j][k][0]+p[j+1]-p[j],f[j+1])), minn(g[j][k-1][1],max(g[j][k][0]+p[k-1]-p[j],f[k-1])); if (g[j][k][1]!=INF ) minn(g[j][k-1][1],max(g[j][k][1]+p[k]-p[k-1],f[k-1])), minn(g[j+1][k][0],max(g[j][k][1]+p[k]-p[j+1],f[j+1])); } int ans=INF; rep(i,0,maxa) ans=min(ans,abs(p[i]-k)+min(g[i][i][1],g[i][i][0])); cout<<ans<<endl; return 0; }