2024牛客五一集训派对day2 Groundhog Looking Dowdy 个人解题思路

前言：

被实验室教练要求要打的这次五一牛客的训练赛，这些区域赛难度的题对于大一的我来说难度实在是太高了，我和我的队友只写了一些非常简单的签到题，其他题目都没怎么看（我们太弱了），但我可以分享一下我能做出来的题的思路。

正文：

题目：

链接：F-Groundhog Looking Dowdy_2024牛客五一集训派对day2 (nowcoder.com)

题意：

告诉你有n天，每天都有j个数字，让你每天选出当天（第i天）的其中1个，让你求出n天中m天（m<=n）选出的数字的最小的数字最大值与最小值的差值。

比如样例，共4天，我们需要选3天，最小的差值当且仅当选1，3，4天时，这时这3天中最大的是3，最小的是1，差值为2。2为最小差值，所以输出2。

思路：

一：

我们不妨定义一个结构体，包含一个数字和它所在的天数。将这些结构体按数字大小排序，这样我们就得到了一串递增或递减的数组，我们要求出的答案一定是这个数组的一段连续的子数组（数组中连续的一小段）的左右两端的差值的绝对值（表示最大值与最小值的差值），同时我们要让这段子数组合理（数组中数字代表的不同天数的个数为m），如此我们就能得到答案。

首先我先考虑了暴力的算法，通过两层循环，第一层找开始的第一个数字，第二层遍历到满足子数组条件的第一个的数字上，两个数字相减就是答案。这个思路显然是没问题的，但是明显两层循环处理1e6的数据量会超时，我们得想办法优化掉暴力的算法。

二：

我们可以发现通过循环遍历找这段数组十分耗时，我们没必要一遍又一遍的从第一层循环的数字开始找，我们可以设计两个指针，一个指向第一个数字，一个指向后面的一个数字，当这段数字满足条件时就记录下这个数字并移动左指针，若不满足则考虑移动右指针，这样的方式叫滑动窗口（不懂的可以看看这篇博客 滑动窗口详解_窗口滑动-CSDN博客）。我们可以通过桶排的方式来记录天数数量，每次移动指针时再判断天数数量是否等于m，在所有符合答案的数字中找最小值输出即可。代码如下。

#include <bits/stdc++.h>
using namespace std;
const int N=2e6+5;
typedef struct node{
    int a;
    int day;
}node;
node b[N];
int book[N];
bool cmp(node x,node y){
    return x.a<y.a;
}
int n,m,ans=1000000000;
int main(){
    cin>>n>>m;
    int cnt=1;
    for(int i=1;i<=n;i++){
        int x;cin>>x;
        for(int j=1;j<=x;j++){
            cin>>b[cnt].a;
            b[cnt].day=i;
            cnt++;
        }
    }
    cnt--;
    sort(b+1,b+cnt+1,cmp);
    for(int i=1,j=m;i<=cnt&&j<=cnt&&i<j;){
        int diff=0;memset(book,0,sizeof(book));
        for(int k=i;k<=j;k++){
            if(!book[b[k].day]){
                diff++;
                book[b[k].day]++;
            }
        }
        if(diff==m){
        //  cout<<b[j].a<<" "<<b[i].a<<endl;
            ans=min(ans,b[j].a-b[i].a);
            j++;
        }
        if(diff>m)i++;
        if(diff<m)j++;
    //  cout<<i<<" "<<j<<" "<<diff<<" "<<endl;
    }
    cout<<ans<<endl;
}

三：

但是这段代码依旧超时了，主要是每次记录天数数量都要从子数组的开始到结束，极大增加了不必要的运算。对于diff，我们可以根据指针的改变来动态维护，这样就避免了不必要的运算，最后结果终于ac了（943ms，比较极限），代码如下：

#include <bits/stdc++.h>
using namespace std;
const int N=2e6+5;
typedef struct node{
	int a;
	int day;
}node;
node b[N];
int book[N];
bool cmp(node x,node y){
	return x.a<y.a;
}
int n,m,ans=1000000000;
int main(){
	cin>>n>>m;
	int cnt=1;
	int diff=0;
	for(int i=1;i<=n;i++){
		int x;cin>>x;
		for(int j=1;j<=x;j++){
			cin>>b[cnt].a;
			b[cnt].day=i;
			cnt++;
		}
	}
	cnt--;
	sort(b+1,b+cnt+1,cmp);
	for(int i=1;i<=m;i++){
		if(!book[b[i].day]){
			diff++;
			book[b[i].day]++;
		}
	}
	int l=1,r=m;
	while(diff<m){
		r++;
		if(!book[b[r].day]){
			diff++;
			book[b[r].day]++;
		}
	}
	while(r<=cnt){
	//	cout<<b[r].a<<" "<<b[l].a<<endl;
		ans=min(ans,b[r].a-b[l].a);
		book[b[l].day]--;
		l++;
		if(book[b[l-1].day]==0) diff--;
		while(diff<m&&r<=cnt){
			r++;
			if(!book[b[r].day]){
				diff++;
				book[b[r].day]++;
			}
			
		}
	}
	cout<<ans<<endl;
}