问题 A: Kill

时间限制: 1 Sec 内存限制: 256 MB

题面

题面谢绝公开。

题解

80%算法

赛时并没有想到正解，而是选择了另一种正确性较对的贪心验证。

对于每一个怪，我们定义它的权值为到结算点的距离。

二分答案，对于每一个人，考虑他能打的所有怪，选择权值最大的怪去打。这样可以尽量将权值小的怪留给后面的人。

然而这样会挂掉。考虑假如结算点在中间，右边怪少人多，左边怪多人少，

而左边一个距离结算点比较近的人可能会抢掉右边一个怪，造成答案不优。

复杂度$O(nmlog)$

100%算法

正解二分加贪心验证。对人的位置和怪的位置分别排序。

二分最终答案。check的时候顺序扫每一个人，顺序打怪即可。可以保证每个人都有怪打。

复杂度$O(nlog)$

代码：

#include<bits/stdc++.h>

#define rint register int

#define ll long long

#define read(A) A=init()

using namespace std;

inline int init()

{

    int a=,b=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')b=-;ch=getchar();}

    while(ch>=''&&ch<=''){a=(a<<)+(a<<)+ch-'';ch=getchar();}

    return a*b;

}

int n,m,s,ans=0x7fffffff;

int p[],q[],w[];

bool vis[];

inline ll get_dis(int x,int y)

{

    return 1ll*abs(q[y]-p[x])+abs(q[y]-s);

}

inline bool check(ll mid)

{

    int j=;

    for(rint i=;i<=n;++i)

    {

        while(j<=m)

        {

            if(get_dis(i,j)<=mid){j++;break;}

            j++;

        }

        if((j==m+)&&(i<n))

            return false;

        if((j==m+)&&(i==n)&&get_dis(n,m)>mid)

            return false;

    }

    return true;

}

int main()

{

    read(n),read(m),read(s);

    for(rint i=;i<=n;++i)read(p[i]);

    for(rint i=;i<=m;++i)read(q[i]);

    ll l=,r=0x7fffffffffffffff;

    sort(p+,p+n+);sort(q+,q+m+);

    while(l<=r)

    {

        ll mid=(l+r)>>;

        if(!check(mid))l=mid+;

        else r=mid-;

    }

    printf("%lld\n",l);

    return ;

}

巴特西

「题解」：Kill

问题 A: Kill

题面

题解

最新文章

热门文章