自动搬运

查看原文

来自洛谷，原作者为

	大宋宝宝 人送外号宋AK,一名11岁的小学生||支持壶关，壶关条件https://www.luogu.com.cn/paste/88dc6t5s

搬运于2025-08-24 23:00:30，当前版本为作者最后更新于2024-08-20 16:54:42，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目传送门

思路

首先把数组排序，然后用双指针维护数组，因为要想最大身高差最小，一定是选排序后在数组里连续的一段最优，其中一些人所在的班级有重复也没关系，可以不带他们拍照。

Code：

#include <bits/stdc++.h>
using namespace std;
int n,s,sum,l=1,ans=INT_MAX,cnt,tong[1001];
//ans表示最终答案，sum表示照片有几个不同班级的人 
struct ts {
	int sg,bj;
	//sg表示学生的身高，bj表示学生的班级 
}a[1000001];
bool cmp(ts a1,ts a2) {
	return a1.sg<a2.sg;
}
int main() {
	cin>>n>>s;
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=s;j++) {
			cin>>a[++cnt].sg;
			a[cnt].bj=i;
			//读入，初始化学生的班级 
		}
	}
	sort(a+1,a+cnt+1,cmp);
	//按升序排序 
	for(int i=1;i<=cnt;i++) {
	//l表示左端点，i表示右端点 
		if(!tong[a[i].bj]) sum++;
		//如果这个学生所在的班级之前没有人在合照里出现过 
		//就让不同班级的人数加一 
		tong[a[i].bj]++;
		//这个班来的人数加一 
		if(sum==n) {
		//如果人齐了 
			while(tong[a[l].bj]>=2) tong[a[l++].bj]--; 
			//就尝试移动左端点，直到再移就不满足要求 
			ans=min(ans,a[i].sg-a[l].sg);
			//如果现在的答案更优，就更新答案 
		}
	}
	cout<<ans;
	//输出 
	return 0;
}

AC记录

本蒟蒻第一次写题解，求过