cf830A Office Keys（贪心+暴力枚举）_office keys cf

传送门

在一个数轴上有 $n$ 个人及 $k$ 把钥匙 $（k\ge n)$，每个人都需要先拿取一把钥匙再到达 $p$ 点，且一把钥匙最多只能被一个人取走，问这些人中需要花费的时间的最大值的最小值是多少。

可以得证在最优的匹配中，每个人及其对应钥匙的连线一定是无交叉的，否则将存在交叉的匹配进行对换后一定比当前方案更优。且最终取得的 $n$ 把钥匙一定是一段连续的区间，因此可直接枚举以哪把钥匙作为连续区间的左端点得到的结果最优。

由于答案很大，因此 $ans$ 的初始化一定要开到足够大。

#include <bits/stdc++.h>
#define int long long
#define endl '\n'

using namespace std;
int a[1010],b[2010];

signed main(){
	int n,k,p;
	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+n+1);
	sort(b+1,b+k+1);
	
	int len=k-n+1;
	int ans=1e18,maxx=0;//ans初值一定要开到足够大 
	for(int start=1;start<=len;start++){//连续区间的左端点 
		maxx=0;
		for(int i=start,j=1;j<=n;i++,j++){//i为钥匙 j为人 
			maxx=max(maxx,abs(b[i]-p)+abs(a[j]-b[i]));
		}
		ans=min(ans,maxx);
	}
	cout<<ans<<endl;
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30