问题 A: Kill
时间限制: 1 Sec 内存限制: 256 MB
题面
题面谢绝公开。
题解
80%算法
赛时并没有想到正解，而是选择了另一种正确性较对的贪心验证。
对于每一个怪，我们定义它的权值为到结算点的距离。
二分答案，对于每一个人，考虑他能打的所有怪，选择权值最大的怪去打。这样可以尽量将权值小的怪留给后面的人。
然而这样会挂掉。考虑假如结算点在中间，右边怪少人多，左边怪多人少，
而左边一个距离结算点比较近的人可能会抢掉右边一个怪，造成答案不优。
复杂度$O(nmlog)$
100%算法
正解二分加贪心验证。对人的位置和怪的位置分别排序。
二分最终答案。check的时候顺序扫每一个人，顺序打怪即可。可以保证每个人都有怪打。
复杂度$O(nlog)$
代码：
#define rint register int
#define ll long long
#define read(A) A=init()
using namespace std;
inline int init()
{
int a=0,b=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')b=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){a=(a<<3)+(a<<1)+ch-'0';ch=getchar();}
return a*b;
}
int n,m,s,ans=0x7fffffff;
int p[5003],q[5003],w[5003];
bool vis[5003];
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=1;
for(rint i=1;i<=n;++i)
{
while(j<=m)
{
if(get_dis(i,j)<=mid){j++;break;}
j++;
}
if((j==m+1)&&(i<n))
return false;
if((j==m+1)&&(i==n)&&get_dis(n,m)>mid)
return false;
}
return true;
}
int main()
{
read(n),read(m),read(s);
for(rint i=1;i<=n;++i)read(p[i]);
for(rint i=1;i<=m;++i)read(q[i]);
ll l=0,r=0x7fffffffffffffff;
sort(p+1,p+n+1);sort(q+1,q+m+1);
while(l<=r)
{
ll mid=(l+r)>>1;
if(!check(mid))l=mid+1;
else r=mid-1;
}
printf("%lld\n",l);
return 0;
}