本文共 2301 字，大约阅读时间需要 7 分钟。

本来都想到二分开始写check函数的,结果脑子一乱觉得不能贪心…

贪心法则

$对于二分的时间x,最左边的人要尽量选最左边的钥匙$

$当最左边的钥匙在最左边人的左边时显然正确,因为后面的人想拿这把要走回来,要走更多的路$

$当最左边的钥匙在最左边人的右边时,需要想一想,我就是这里没想通。$

也许你会说,这个时候去拿右边的钥匙会不会更优?

$你要这么想,你能拿到右边的钥匙,那么右边的人肯定也能拿到这把钥匙$

$但是你要是拿左边一点,后面的人$可能$就拿不到这把钥匙,因为后面的人需要走回来$

#include 
   
    using namespace std;const int maxn=2e5+10; #define int long longint n,k,p,ans,vis[maxn],a[maxn],b[maxn];bool isok(int s){	int index=1;	for(int i=1;i<=n;i++)	{		while( abs(a[i]-b[index])+abs(p-b[index]) > s)		{			index++;			if(index>k)	return false;		}		index++;	}	return true;}signed main(){	cin >> n >> k >> p;	for(int i=1;i<=n;i++)	cin >> a[i];	for(int i=1;i<=k;i++)	cin >> b[i];	sort(a+1,a+1+n);	sort(b+1,b+1+k);	int l=0,r=2e9,mid;	while(r>=l)	{		mid = (l+r)>>1;		if( isok(mid) )	r=mid-1,ans=mid;		else	l=mid+1;		}	cout<
   

$还有dp的,但实际上也是基于上面的结论,左边的人用左边的$

$设dp[i][j]为前i个人用前j把钥匙$

$那么每次可以dp[i][j]=dp[i][j-1],不使用第j把钥匙$

$用第j把钥匙,dp[i][j]=max(dp[i-1][j-1],abs(a[i]-b[j])+abs(p-b[j]))$

#include 
   
    using namespace std;typedef long long ll;const int maxn=2009;ll dp[maxn][maxn],a[maxn],b[maxn],n,k,p;int main(){	cin >> n >> k >> p;	for(int i=1;i<=n;i++)	cin >> a[i];	for(int i=1;i<=k;i++)	cin >> b[i];	sort(a+1,a+1+n);	sort(b+1,b+1+k);	memset(dp,20,sizeof(dp));	for(int j=0;j<=k;j++)	dp[0][j]=0;	for(int i=1;i<=n;i++)	for(int j=i;j<=k;j++)		dp[i][j]=min(dp[i][j-1],max(dp[i-1][j-1],abs(a[i]-b[j])+abs(p-b[j])) );	cout<
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/107216571 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！