解法

假的单调队列哦。

考虑将每个类别元素的下标记好，然后先把每个类别标号最小的放入 multiset，然后对答案进行更新：每次取出最大和最小值做差更新，然后把最小值的下标更新后重新扔进 multiset 中。如果 multiset 中所有的类别都已经枚举完毕，那么直接跳出循环进行输出即可。

代码

// P2564.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct node
{
    ll typ, val, dep;
    bool operator<(const node &nd) const { return val < nd.val; }
};
int n, k;
vector<int> typs[100];
multiset<node> st;

int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= k; i++)
    {
        int ti;
        scanf("%d", &ti);
        while (ti--)
        {
            int num;
            scanf("%d", &num), typs[i].push_back(num);
        }
        st.insert(node{i, typs[i][0], 0});
    }
    ll ans = 0x3f3f3f3f3f3f3f3f;
    int full = 0;
    while (full < k)
    {
        node small = *st.begin(), biggest = *(--st.end());
        ans = min(ans, biggest.val - small.val);
        st.erase(st.begin());
        if (small.dep + 1 < typs[small.typ].size())
            small.val = typs[small.typ][small.dep + 1], small.dep++;
        else
            full++;
        st.insert(small);
    }
    node small = *st.begin(), biggest = *(--st.end());
    ans = min(ans, biggest.val - small.val);
    printf("%lld", ans);
    return 0;
}