【hash表】收集雪花

【哈希和哈希表】收集雪花

题目描述

不同的雪花往往有不同的形状。在北方的同学想将雪花收集起来，作为礼物送给在南方的同学们。一共有n个时刻，给出每个时刻下落雪花的形状，用不同的整数表示不同的形状。在收集的过程中，同学们不希望有重复的雪花。你可以从任意a时刻开始，在b时刻停止。a到b时刻中间的雪花也都将被收集。他们希望收集的雪花最多。

输入

第一行一个正整数n；第2行到第n+1行表示n个时刻雪花的形状。

输出

最多能收集雪花的数量。

样例输入

5

1 2 3 2 1

样例输出

3

提示

n≤1e6，xi≤1e9

---

【题解】

这个题目其实用的是一种的hash方式，其实就是我们常用的离散化操作。

1、另外一个数组存放相同数据，然后进行排序。

2、因为大小相同可以看成一个数，所以相同的话，可以用lower_bound来写，因为是大于等于某个数，等于可以看成对应的大小关系。

3、然后进行双指针方法来跑最大区间的不同种类的个数。

---

【代码】

 #include<cstdio>

 #include<bitset>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 typedef unsigned long long ULL ;

 const int N = 1e6+;

 const int M = 5e6+;

 const ULL base = ;

 int a[N],c[N],H[M],n;

 ULL b[N];

 void Dispersed(){

     sort( b +  , b +  + n );

     for(int i=;i<=n;i++){

         c[i] = lower_bound(b+,b++n,a[i]) - (b+);

     }

 }

 int main()

 {

     ios_base :: sync_with_stdio(false);

     cin.tie(NULL) , cout.tie(NULL) ;

     cin >> n ;

     for(int i=;i<=n;i++)   cin >> a[i] ,b[i] = a[i];

     Dispersed();

     int res =  ;

     for(int i=,j=;j<=n;j++){

         H[ c[j] ] ++ ;

         while( H[c[j]] >  ) H[ c[i++] ] --;

         res = max( res , j-i+) ;

     }

     printf("%d\n",res );

     return ;

 }