自动搬运

查看原文

来自洛谷，原作者为

	true_kun 高贵的初中生，没人三国杀（真_鸡-甄_姬）

搬运于2025-08-24 22:59:42，当前版本为作者最后更新于2025-07-23 20:29:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

使满足条件的值最小，这个对答案的定义很二分。

我们考虑对于每一个机器而言真正影响他的芯片功率差的只有最小的两块电池。一块电池如果是芯片中最小的那个，那么同一机器的另一块芯片的最小的电池一定是这块电池的前一个或后一个，换句话说，每次我们选取一个机器两个机器的最小电池时，一定选取两个相邻的电池。

反证法证明：如果这么做不一定是最优的，那么一定有与第 $i$ 块电池相隔几个位置的电池与它匹配在同一机器里，这么做一定不会让答案变小，充其量与我们的决策答案一致，故得证。

我们将数组排好序，如果相邻的两个电池差小于我们二分的答案，说明这两个电池可以作为同一机器两块芯片的最小电池，我们将合法的组数加一。

特别注意！ 并不是只要组数足够就合法的，我们观察下面一组样例。 见代码。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k,m;
int a[1000005];
bool check(int mid){
	int t=0;
	for(int i=1;i<m;i++){
		if(a[i+1]-a[i]<=mid) t++,i++;
		if(i>=t*2*k+1){
			return 0;//它比组数乘电池数乘二的值还要大，前面一定有没有处理的，所以直接舍去即可。
		}
	}
	if(t>=n) return true;
	else return false;
}
signed main(){
	cin>>n>>k;
	m=2*n*k; 
	for(int i=1;i<=m;i++) cin>>a[i];
	sort(a+1,a+1+m);
	int l=0,r=1e18+1;
	while(l<r){
		int mid=(l+r)>>1;
		if(check(mid)){
			r=mid;
		}else{
			l=mid+1;
		}
	}
	cout<<l;
	return 0;
}
/*
2 2
1 2 10 12 15 17 20 21
这组数据答案是2，但是为什么不是1呢？
我们考虑它为什么不合法，因为在以20 21开头
的芯片中他们两个不是最小电池，无法左右机器
功率，如何判断一个两个电池是否是还没有被安
排的电池，这个东西很难判断（我卡了好久），
我们换个思路，只要比它小的电池全部被处理结
束了就可以。如何处理，见上面代码。
*/