2020牛客暑期多校训练营（第九场）F-Groundhog Looking Dowdy

题目大意

有n天，每天穿一件衣服，第天有件衣服可以穿，穿第件衣服的的权值为。
求其中任意m天中，所穿衣服的权值最大值与最小值的最小差。

解题思路

我们要做的是最小化最大最小值之差，所以必要的肯定是把所有衣服按照权值从小到大排个序。
我们可以把每件衣服打一个标记，记录一下是从哪一天来的。然后在里面维护一个来自不同的天的个数为m，这些衣服的权值必定是大于左端点小于右端点，直接求ans即可。

AC代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e6+10;
struct node
{
    int x,y;
} a[N];
int b[N],l=1,r,x,tot,ans=1e9;
bool cmp(node x,node y)
{
    return x.y<y.y;
}
int main()
{
    int n,m,x,i,j;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&x);
        for(j=1;j<=x;j++)
        {
            scanf("%d",&a[++tot].y);
            a[tot].x=i;
        }
    }
    sort(a+1,a+tot+1,cmp);
    x=0;
    while(x<m)
    {
        r++;
        if(!b[a[r].x]) b[a[r].x]++,x++;
    }
    while(r<=tot)
    {
        ans=min(ans,a[r].y-a[l].y),b[a[l].x]--,x--,l++;
        if(!b[a[l].x]) b[a[l].x]++,x++;
        while(x<m && r<=tot)
        {
            r++;
            if(!b[a[r].x]) b[a[r].x]++,x++;
        }
    }
    printf("%d\n",ans);
}