[CSP-S模拟测试]:kill（二分答案+贪心）

题目传送门（内部题50）

输入格式

第一行包含四个整数$n,m,s$，表示人数、怪物数及任务交付点的位置。
第二行包含$n$个整数$p_1,p_2,...,p_n$。
第三行包含$n$个整数$q_1,q_2,...,q_n$。

输出格式

输出一行包含一个整数$ans$，表示答案。

样例

样例输入：

2 4 5
2 10
6 1 4 8

样例输出：

数据范围与提示

样例解释：

第一个人打位置为$4$的怪物，第二个人打位置为$8$的怪物，前者花$3$的时间，后者花$5$的时间，该方案对应的时间为$5$，且是一个最优方案。

数据范围：

对于所有数据：$1\leqslant p_i,q_i,s\leqslant {10}^9$。

题解

考虑二分答案，那么如何$judge$。

贪心解决，对于位于$s$右边的人，我们让他尽可能的打左边的怪兽，如果不能打就打右边的；反之同理。

注意边界问题即可。

时间复杂度：$\Theta(n\log \max(p_i,q_i,s)$。

期望得分：$100$分。

实际得分：$100$分。

代码时刻

#include<bits/stdc++.h>

using namespace std;

int n,m,s;

long long p[5001],q[5001],dis[5001];

bool judge(long long x)

{

	int lft=0,rht=m+1;

	for(int i=1;i<=n;i++)

	{

		if(p[i]>s)break;

		while(abs(p[i]-q[lft])+dis[lft]>x)

		{

			lft++;

			if(lft>m)return 0;

		}

		lft++;

		if(lft>m)return 0;

	}

	lft--;

	for(int i=n;i;i--)

	{

		if(p[i]<=s)break;

		while(abs(p[i]-q[rht])+dis[rht]>x){rht--;if(!rht)return 0;}

		rht--;

		if(!rht)return 0;

	}

	rht++;

	if(rht<=lft)return 0;

	return 1;

}

int main()

{

	scanf("%d%d%d",&n,&m,&s);

	for(int i=1;i<=n;i++)scanf("%lld",&p[i]);

	for(int i=1;i<=m;i++)scanf("%lld",&q[i]);

	sort(p+1,p+n+1);

	sort(q+1,q+m+1);

	for(int i=1;i<=m;i++)dis[i]=abs(q[i]-s);

	dis[0]=dis[m+1]=1LL<<60;

	long long lft=0,rht=1LL<<60;

	while(lft<rht)

	{

		long long mid=(lft+rht)>>1;

		if(!judge(mid))lft=mid+1;

		else rht=mid;

	}

	cout<<lft<<endl;

	return 0;

}

rp++

巴特西