Codeforces Round #424 (Div. 2, rated, based on VK Cup Finals)D. Office Keys（二分＋贪心）

时间：2022-12-30 10:02:48

题目链接

http://codeforces.com/contest/831/problem/D

题目大意

给你n个人k把钥匙和门的位置p，都在一条线上。
人要进门都需要一把钥匙，人移动一个单位需要1单位的时间
问所有人都进门最少需要多少时间？（保证k>=n）

思路

由于给定的人和钥匙的位置都是随机的，要求最短时间，杂乱无章的顺序不好处理，我们把人和钥匙都排个序
排好序后，我们应该想到，钥匙要先给谁又不影响其他人拿钥匙
这时候应该要想到贪心了

贪心

策略

由于时间是连续的，我们直接二分时间t，最小时间其实就是最后一个人所花的时间
把人和钥匙都排序后，我们用一层循环i扫钥匙，用一个从0开始的光标pos指向人数组，如果人pos拿钥匙i再到门所花时间<=t, 那就把钥匙i给人pos， 再++pos, 直到所有人都进门

证明

由于人和钥匙都是按坐标排序的， 第i把钥匙可以给人pos，也可以给人pos+1，但是如果给了人pos+1， 那么人pos就有可能要花更多的时间去拿别的钥匙（与门的位置无关，可以自己动手画一画）
但是这个贪心策略是 伪-选择当前情况的最优解，因为在钥匙充足的情况下，人pos不一定要选择钥匙i，因为可能钥匙i不是最优选择，也就是说人pos选择钥匙i可能绕了远路
但是我们的策略最优的是什么？是保证后面不会因为前面的选择走更远的路，这样的话，不断二分的过程中，我们会不断逼近最优解

代码

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;//注意要开long long
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll pe[1005], key[2005];
ll n, k, d;

bool check(ll x)
{
    int pos=0;
    for(int i=0; i<k; ++i)
    {
        if(abs(d-key[i])+abs(pe[pos]-key[i]) <= x)++pos;
        if(pos>=n)return true;
    }
    return false;
}

int main()
{
    scanf("%I64d%I64d%I64d", &n, &k, &d);
    for(int i=0; i<n; ++i)
        scanf("%d", pe+i);
    for(int i=0; i<k; ++i)
        scanf("%d", key+i);
    sort(pe, pe+n);
    sort(key, key+k);
    ll l=0, r=INF, mid;
    while(l < r)//二分求上界
    {
        mid = (l+r)/2;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    printf("%I64d\n", (l+r)/2);
    return 0;
}

收获

  1. 不能第一时间判断是否会爆int而wa， 下次注意
  2. 二分又写挫了，下次一定要判断好是求上界还是下界再写，可以看这个博客复习http://www.cnblogs.com/ider/archive/2012/04/01/binary_search.html#3698112
  3. 贪心并不一定要马上得到最优解， 还可以选取一定策略后用二分去逼近答案
标签：

相关文章