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;
}