UVA11572 唯一的雪花 Unique Snowflakes 题解

zhenliu · 2021-05-07 17:25:12 · 题解

前言

这道题跟逛画展很像，一样可以用双指针来做。不过前者的限制是要求每个种类包含一个，而此题要求不能包含相同种类，所以只用改一下更新答案的条件就好啦。
你问双指针是什么？：尺取法（双指针）洛谷日报
思路
设置 l,r 两个指针，可以知道，如果答案合法，那么 r+1-l 永远是优于 r-l 的

所以，当答案合法时（没有重复的种类），更新答案，并将 r 右移。当答案不合法时，将 l 不断右移，去重，直到答案合法。

代码

#include<bits/stdc++.h>
#define RI register int
using namespace std;
int n,t,cnt[1000005],a[1000005];
int main(){
  scanf("%d",&t);
  while(t--){
      int l=1,r=1,repeat=0,maxans=-0x3f3f3f3f;//repeat表示有重复的雪花种类个数 
      memset(cnt,0,sizeof(cnt));
      scanf("%d",&n);
      for(RI i=1;i<=n;i++)scanf("%d",&a[i]);
      cnt[a[1]]=1;
      while(l<=r&&r<=n){
      //一点废话：为什么r>n就退出呢？会不会出现r>n了后，l右移还能更新答案的情况呢？
      //因为r>n肯定是前一个合法方案把r++变过来的。相当于l=x，r=n的时候肯定有一个合法解。所以后面l右移了就不会有更大的合法解了 
          if(repeat==0){//没有重复的雪花，更新答案,并将r往右移找更大的答案 
              maxans=max(maxans,r-l+1);
              r++;
              if(++cnt[a[r]]>1)repeat++;
          }
          else{
              if(--cnt[a[l]]==1)repeat--;//有重复的雪花，将l往右移去重 
              l++;
          }
      }
      printf("%d\n",maxans);
  }
  return 0;
}

Thanks for Watching

UVA11572 唯一的雪花 Unique Snowflakes 题解

前言

思路

代码