【贪心+二分查找】Office Keys CodeForces - 830A

￡神魔★判官ぃ 2022-06-08 22:59 153阅读 0赞

Think:  
1知识点：贪心+二分查找  
2题意：n个人初始出发位置，m把钥匙放置位置，办公室位置p，询问在所有人取到钥匙之后到达办公室的最短时间  
3反思：  
1>初始忘记排序  
2>最初选择的贪心策略无法得到全局最优解  
4解题方法：  
二分枚举逼近可能的最短时间，然后试探当前选择的时间是否可以满足所有人取到钥匙后到达办公室

[vjudge题目链接][vjudge]

[可参考博客][Link 1]

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    
    using namespace std;
    
    typedef long long LL;
    
    const int N = 1014;
    const int M = 2014;
    
    int n, m, p, a[N], b[M];
    
    bool Check(LL ans);
    
    int main(){
        while(~scanf("%d %d %d", &n, &m, &p)){
            for(int i = 0; i < n; i++)
                scanf("%d", &a[i]);
            for(int i = 0; i < m; i++)
                scanf("%d", &b[i]);
            sort(a, a+n);
            sort(b, b+m);
            LL l = 0, r = 2e9, mid, ans;
            while(l <= r){
                mid = (l+r)>>1;
                if(Check(mid)){
                    ans = mid;
                    r = mid-1;
                }
                else
                    l = mid+1;
            }
            printf("%lld\n", ans);
        }
        return 0;
    }
    bool Check(LL ans){
        int i, pos = -1;
        for(i = 0; i < n; i++){
            while(pos < m){
                pos++;
                if(abs(a[i]-b[pos])+abs(b[pos]-p) <= ans)
                    break;
            }
            if(pos >= m)
                return false;
        }
        return true;
    }

[vjudge]: https://vjudge.net/problem/CodeForces-830A
[Link 1]: http://blog.csdn.net/fsmm_blog/article/details/76034139