题目：
分析：
30%dfs暴搜，60%我也不知道。。。（但如果这道题是求时间总和最小的话可以用费用流得60分）
100%：贪心+二分
显然满足单调性：时间越大，每个人的选择范围就越广，越有可能实现。
想到二分很容易，但是怎么check呢？每个人都对应着选择一个打卡机，可是具体应该怎么分配呢？
显然一个人对于很远的打卡机，是不会绕路去的，而选择离自己最近的打卡机又可能会出现和别人争夺的情况。
现在我们知道答案了，对于最左边的一个人来说，我们一定是希望他尽量选择的打卡机是靠左边的，并且越左越好，为什么呢？
因为他选了可以成立的左边的打卡机，还使下一个人拥有了更多的选择，明显是在答案固定的情况下是最优的方案。
于是对人和打卡机排序，从小到大地选择打卡机，一个人能够选择一个打卡机，当且仅当计算出的答案<=mid，二分即可。
/* 二分+贪心 */ #include<bits/stdc++.h> using namespace std; #define N 100005 #define inf 2100000000 #define ll long long int n,m,a[N],b[N],ans=inf,vis[N],pos; bool check(ll x) { int i,j=1; for(i=1;i<=n;i++){//每个人贪心选到第一个离他最近且满足条件的打卡机 while(abs(a[i]-b[j])+abs(b[j]-pos)>x && j<=m) j++; if(j>m) return false; j++; } return i==n+1; } int main() { freopen("work.in","r",stdin); freopen("work.out","w",stdout); scanf("%d%d%d",&n,&m,&pos); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=m;i++) scanf("%d",&b[i]); sort(a+1,a+1+n); sort(b+1,b+1+m); ll l=0,r=inf; while(l<r){ ll mid=(l+r)>>1; if(!check(mid)) l=mid+1; else r=mid,ans=mid; } printf("%d ",ans); } /* 2 2 10 9 11 15 7 10 10 900 34 656 34 87 456 23 67 789 244 675 384 56 4 887 56 203 67 789 24 650 915 3 5 4 9 2 1 7 0 8 8 2 */