首页 > 代码库 > poj 3320 复习一下尺取法
poj 3320 复习一下尺取法
尺取法(two point)的思想不难,简单来说就是以下三步:
1。对r point在满足题意的情况下不断向右延伸
2。对l point前移一步
3. 回到1
two point 对连续区间的问题求解有其独到之处 复杂度为0(n) 很实用的
#include<iostream> #include<map> #include<set> #include<vector> #include<cstdio> #define inf 1000002 using namespace std; int a[inf]; int main() { //cin.sync_with_stdio(false); int n; set<int> all; while(~scanf("%d",&n)) { all.clear(); map<int,int> mapp; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); all.insert(a[i]); } int len = all.size(); int e,num,s; s = e = 1; num = 0; int minlen = inf; while(1) { while(num < len && e<=n)// 向右延伸 { if(mapp[a[e++]]++ == 0) { num++; } } if(num < len) break;// 延伸不下去的时候 要结束啦 minlen=min(minlen, e-s); if(--mapp[a[s++]] == 0)// letf point 的更新 num--; } cout<<minlen<<endl; } }
poj 3320 复习一下尺取法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。