牛客多校第九场 Groundhog Looking Dowdy（双指针，卡常）

本文主要是介绍牛客多校第九场 Groundhog Looking Dowdy（双指针，卡常），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：
每天有一些衣服和其价格。
一共n天，你可以从其中选m天，每天指定一个衣服。要求m天中指定衣服的最大值与最小值差最小。

思路：
特别卡常。只能将所有衣服按照价格和日期存下来，再从小到大排序，算出每个衣服第一个离他m天数的衣服，这就对应最小价格。
这个过程可以双指针维护。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <vector>using namespace std;
typedef long long ll;
const int maxn = 2e6 + 7;
const int mod = 998244353;int vis[maxn];
struct Node {int id,x;
}a[maxn];int cmp(Node a,Node b) {if(a.x == b.x) return a.id < b.id;return a.x < b.x;
}int main() {int n,m;scanf("%d%d",&n,&m);int cnt = 0;for(int i = 1;i <= n;i++) {int amt;scanf("%d",&amt);for(int j = 1;j <= amt;j++) {int x;scanf("%d",&x);a[++cnt] = {i,x};}}sort(a + 1,a + 1 + cnt,cmp);int l = 1,now = 0;int ans = 1e9;for(int i = 1;i <= cnt;i++) {vis[a[i].id]++;if(vis[a[i].id] == 1) {now++;if(now >= m) {ans = min(ans,a[i].x - a[l].x);}}while(now >= m) {vis[a[l].id]--;if(vis[a[l].id] == 0) now--;l++;}}printf("%d\n",ans);return 0;
}

这篇关于牛客多校第九场 Groundhog Looking Dowdy（双指针，卡常）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---