【二分+貪心】Codeforces830A[Office Keys]題解

題目概述

有 n 個人，位置在 ai ， m 把鑰匙，位置在 bi 以及一扇門，位置在 p ，一個人出門需要先拿鑰匙再出門，時間為 |ai−bj|+|bj−p| 。同一時刻可以有任意個人出門，但是鑰匙隻能一個人使用，求最少時間。

解題報告

要求最大值最小，是以用二分枚舉答案 mid 。然後問題是怎麼判斷是否可行，由于是直線距離，根據貪心，我們将 a 和 b 排序。

有一個結論：如果 i 選 j 不滿足，則 i+1 選 j <script type="math/tex" id="MathJax-Element-13">j</script> 也不會滿足，這個很顯然。那麼隻需要用two-point就可以很快驗證了。資料很小感覺本意應該是給我們寫DP的吧……

示例程式

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=,maxm=;

int n,m,p,a[maxn+],b[maxm+];

inline int abs(int x) {if (x<) return -x;return x;}
bool check(int MAX)
{
    for (int i=,j=;i<=n;i++)
    {
        while (j<=m&&abs(a[i]-b[j])+abs(p-b[j])>MAX) j++;
        if (j>m) return false;j++;
    }
    return true;
}
int main()
{
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    scanf("%d%d%d",&n,&m,&p);
    for (int i=;i<=n;i++) scanf("%d",&a[i]);
    for (int i=;i<=m;i++) scanf("%d",&b[i]);
    sort(a+,a++n);sort(b+,b++m);
    int L=,R=;
    while (L<=R)
    {
        int mid=L+(R-L>>);
        if (check(mid)) R=mid-; else L=mid+; 
    }
    return printf("%d\n",L),;
}