尺取法

题意：一共有m天，每天有k[i]件衣服，每条衣服有值a[i],欲选取n件衣服，使得选择出的n条衣服的值的最大差值最小。
​
解题思路：采用尺取法，根据区间的特征交替推进左右端点求解，可以避免了大量的无效枚举，本题区间间枚举都是根据区间特征有方向的枚举。适用于选取区间有一定规律，或者说所选取的区间有一定的变化趋势的情况，通俗地说，在对所选取区间进行判断之后，我们可以明确如何进一步有方向地推进区间端点以求解满足条件的区间，即通过改变两端点的位置得到有效解答。

#include<bits/stdc++.h>
using namespace std;
const int MAX = 2e6+50;
int enen;
struct Node
{
    int tt;        /// 存值
    int ii;        /// 存天数
}M[MAX];        

bool cmp(Node ta,Node tb)/// 按值升序
{    
    return ta.tt < tb.tt;
}
int shu[MAX];        /// 计算某天出现的次数

int main()
{
    int day,m;
   cin>>day>>m;
    for(int i=1;i<=day;++i)
    {
        int n;
    cin>>q;
        while(q--)
        {
            int t;
            cin>>t;
            enen++;
            M[enen].tt = t;
            M[enen].ii = i;
        }
    }
    sort(M+1,M+enen+1,cmp);
    int L = 0;
    int R = 0;
    int ans = INF;
    int sum = 0;
    while(1)
    {            
        R++;
        while(R <= enen && sum < m)
        {
            if(shu[M[R].ii]==0)
            {
                sum++;
            }
            shu[M[R].ii]++;
            if(sum==m)break;
            R++;
        }
        if(R>enen)
        break;
        L++;
        while(L <= R && sum==m)
        {
            ans=min(ans ,M[R].tt - M[L].tt);
            if(shu[M[L].ii]==1)
            {
                sum--;
            }
            shu[M[L].ii]--;
            if(sum!=m)
                    break;
            L++;
        }
    }
    cout<<ans<<endl;
    return 0;
}