题解：P10710 [NOISG2024 Prelim] School Photo

大宋宝宝 · 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记录

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