2020暑期多校D9-F 思路+证明

2020暑期多校D9-F 思路+证明
主为自用，欢迎指正。

https://ac.nowcoder.com/acm/contest/5674/F

前置知识：
尺取法：一种反复推进区间的头尾，求出满足条件的最小区间的技巧。

题意：
从n天中选m天，要让m天所穿的衣服价值的最大值与最小值差值最小。

思路：
由于每天有不定件衣服可选取，但是最多只有2e6件衣服，一维数组完全存得下，故想到排序，暴力每段长度为m的区间，若天数少了则向右拓展，维护最大值与最小值之间的差值。时间复杂度为O(n*n)。
后来直接TLE，故决定用尺取降低时间复杂度，尺取的核心在于对满足与不满足条件时的左右区间端点进行修改，故O（n）时间复杂度即可。

代码步骤：
将所有衣服按照价值升序存至一维数组，随后尺取，详细可见代码注释。

AC代码：

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#include<map>
#include<math.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 2e6 + 10;
int Case;
int n, m;
int num;
int min1, max1 = 0;
int count1 = 0;
int ha[N];

struct point1 {
    int v;
    int l;
}p[N];

bool cmp1(point1 a, point1 b) {
    return a.v < b.v;
}

void solve() {
    int res = INF;
    int cou = 0;    //区间内不同天数
    int s = 1;
    for (int t = 1; t <= count1; t++) {
        if (!ha[p[t].l])
            cou++;
        ha[p[t].l]++;        //选择该天的衣服件数
        while (cou == m) {
            res = min(res, p[t].v - p[s].v);    //选取最小差值
            ha[p[s].l]--;    //则第p[s].l天的衣服可去掉
            if (!ha[p[s].l])//若去掉第s小件衣服后，改天p[s].l不再被选取则选取不同天数减一
                cou--;
            s++;            //每次cou==m，必定使原点前进
        }
    }
    printf("%d\n", res);
}

int main() {
    scanf("%d%d", &n, &m);
    memset(p, 0, sizeof(p));
    memset(ha, 0, sizeof(ha));
    for (int i = 1; i <= n; i++) {
        scanf("%d", &num);
        for (int j = 1; j <= num; j++) {
            scanf("%d", &p[++count1].v);
            p[count1].l = i;
        }
    }
    sort(p + 1, p + count1 + 1, cmp1);
    solve();
    //    for (int i = 0; i < count1; i++)
    //        printf("%d", p[i].v);

}

简单图证：

注：
数据给的很差，默认最小价值差为，最小价值衣服为端点至m件不同衣服的最大值的查值。