原题链接：https://ac.nowcoder.com/acm/contest/5674/F

题目描述

土拨鼠（Groundhog）发现苹果（Apple）比以前对他更不亲近了。同时他发现他的打扮过时了。但土拨鼠过于懒惰，他只列出了接下来n天能穿的衣服。在第i天，他的第j件衣服的权值为 $图片说明$ 。在这n天里他要选择m天于苹果外出。但他想知道这m天里所穿衣服的权值的最大值与最小值的差的最小值。

输入描述

第一行输入两个整数n,m；
接下来n行每行先输入一个整数k，再输入k个整数，分别表示衣服的权值。

输出描述

输出一个整数作为结果。

数据范围

$图片说明$ $图片说明$ $图片说明$ $图片说明$ 衣服总量不超过 $图片说明$

样例

输入
4 3
1 3
2 8 6
1 2
3 1 7 5
输出
2
说明：
土拨鼠选择在第1,3,4天与苹果外出，他分别选择权值为3,2,1的衣服，这样的组合差值最小，为3-1=2。

题解思路

首先看题发现要求差，所以首先要把数据存下来，但n和k的范围会使你放弃用二维的念头。仔细一看会发现，衣服总量只有 $图片说明$ ,所以暂时可以用一维数组存放。但衣服穿过以后是不能再穿的，所以不能光记录权值，还要记录在那一天穿了这件衣服。
在我们通过结构体标记权值和那一天穿的该衣服之后，以权值大小为依据对数组进行排序。然后通过制造并移动满足天数为m的区间[L,R]来确定最终答案。
~~事实证明，不是所有题目都像CF（即codeforces）上那么严谨，这道题可以用最小值排序水过。~~（我什么都没说）

参考代码

标准版

//（参考了奆佬的代码）
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=2e6+6;
struct node
{
    int id,sum;
}a[MAXN];
bool cmp(node x,node y)
{
    return x.sum<y.sum;
}
int n,m,k,len,x,v[MAXN];
int ans=1e9;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&k);
        for(int j=1;j<=k;j++)
        {
            scanf("%d",&x);
            a[++len].sum=x
            a[len].id=i;
        }
    }
    sort(a+1,a+len+1,cmp);
    int l=1,r=0,tmp=0;
    while(tmp<m)
    {
        r++;
        if(!v[a[r].id])
        {
            v[a[r].id]++;
            tmp++;
        }
    }//找到第一个符合条件的
    for(l,r;r<=len;)
    {
        ans=min(ans,a[r].sum-a[l].sum);
        v[a[l].id]--;
        tmp--;
        l++;
        if(!v[a[l].id]) v[a[l].id]++,tmp++;
        while(tmp<m&&r<=len)
        {
            r++;
            if(!v[a[r].id])
            {
                v[a[r].id]++;
                tmp++;
            }
        }
    }
    printf("%d\n",ans);
}

水题版

#include <bits/stdc++.h>
using namespace std;

int n,m,k,cnt;
long long a[1000002],minn,ans[1000010];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&k);
        minn=0x3f3f3f3f3f;
        for(int j=1;j<=k;j++)
        {
            scanf("%d",&a[j]);
            minn=min(minn,a[j]);
        }
        ans[++cnt]=minn;
    }
    sort(ans+1,ans+n+1);
    printf("%lld",ans[m]-ans[1]);
}

Groundhog Looking Dowdy