衡水如何做企业网站,江苏和城乡建设厅网站,论坛网站前置审批,优惠建设网站书上把这种问题叫做滑动窗口问题.
我的想法是先进行离散化,然后用一个数组记录元素出现的位置,如果判断某个元素已经出现,就将左端点移到上次出现的位置的后面.每次出现重复元素的时候判断一下答案.我觉得这样的复杂度是最低的.
#includecstdio
#includecstringcstdio
#includecstring
#includealgorithm
#includeclimits
#includecctype
#includequeue
#includesetusing namespace std;typedef long long ll;
const int INF0x3f3f3f3f;
const int MAXN1e65;int a[MAXN],b[MAXN];
int vis[MAXN];
int n,m;
int ans;int main()
{int T;scanf(%d,T);while(T--){scanf(%d,n);for(int i0;in;i) {scanf(%d,a[i]);b[i]a[i];}sort(b,bn);munique(b,bn)-b;for(int i0;in;i){a[i]lower_bound(b,bm,a[i])-b;}memset(vis,-1,sizeof(vis));int l0,r0; ans0;while(rn){if(vis[a[r]]!-1){ansmax(ans,r-l);for(int il;ivis[a[r]];i){vis[a[i]]-1;}lvis[a[r]]1;vis[a[r]]r;r;}else{vis[a[r]]r;r;}}ansmax(ans,r-l);printf(%d\n,ans);}return 0;
}
出现了一个问题就是我刚开始标记的位置可能为0,可是我判断元素出现也是用的0,然后就出现错误了,这是一种危险的做法,以后还是尽量用-1,也挺方便的.
还有就是每次出现重复元素的时候才判断答案,可是如果一直没有出现重复答案的话就有可能没有更新答案,所以在最后要记得更新答案.
看了一下书上的做法,一种用的是set,我觉得那个复杂度挺高的,可是人家也能过.还有一种用的map,我觉得用map也挺好,他还用了一个数组,我觉得用map的话就没有必要用数组记录了,也不用进行离散化了. 发现map可以进行判断值是否出现过,之前都不知道.
我用map又写了一个.
#includecstdio
#includecstring
#includealgorithm
#includeclimits
#includecctype
#includequeue
#includeset
#includemapusing namespace std;typedef long long ll;
const int INF0x3f3f3f3f;
const int MAXN1e65;int a[MAXN];
int n,m;
int ans;
mapint,int vis;int main()
{int T;scanf(%d,T);while(T--){vis.clear();scanf(%d,n);for(int i1;in;i) {scanf(%d,a[i]);}int l1,r1; ans0;while(rn){if(vis[a[r]]!0){ansmax(ans,r-l);for(int il;ivis[a[r]];i){vis.erase(a[i]);}lvis[a[r]]1;vis[a[r]]r;r;}else{vis[a[r]]r;r;}}ansmax(ans,r-l);printf(%d\n,ans);}return 0;
}
