苏州吴江保洁公司,c盘优化大师,王占山,阿里巴巴运营免费教程CodeForces - 616D Longest k-Good Segment
题意#xff1a;
有包含n个数的序列a#xff0c;求能找到最长的区间包含不超过k个不同的元素。
题解#xff1a;
尺取法#xff0c;先固定L#xff0c;然后移动R#xff0c;R每次移动#xff0c;当超过k后#xff0c;L再…CodeForces - 616D Longest k-Good Segment
题意
有包含n个数的序列a求能找到最长的区间包含不超过k个不同的元素。
题解
尺取法先固定L然后移动RR每次移动当超过k后L再移动
代码
#includebits/stdc.h
#define debug(a,b) printf(%s %d\n,a,b);
typedef long long ll;
using namespace std;inline int read(){int s0,w1;char chgetchar();while(ch0||ch9){if(ch-)w-1;chgetchar();}while(ch0ch9) ss*10ch-0,chgetchar();//s(s3)(s1)(ch^48);return s*w;
}
const int maxn5e59;
int a[maxn];
int q[maxn];
int iff[10000009];
int L,R;
int main()
{int n,k;nread();kread();for(int i1;in;i)scanf(%d,a[i]);int l1,r1;L1,R1;int maxx0;int tot1;iff[a[1]]1;while(lrrn){while(totkrn){r;if(iff[a[r]]0){tot;iff[a[r]];if(totk)break;if((r-l)(R-L)){Ll;Rr;}}else {iff[a[r]];if(totk)break;if((r-l)(R-L)){Ll;Rr;}}}iff[a[l]]--;if(iff[a[l]]0)tot--;l;}coutL Rendl;
}
