JZOJ 4911 【NOIP2017模拟12.3】人生的叹息

JZOJ 4911 【NOIP2017模拟12.3】人生的叹息

人生的叹息

题目大意

给出一个长度为 n $n$的序列A$A$，定义一段序列的冲突值为序列中两两元素相同的对数，要求将序列分成若干段，使得每一段序列的冲突小于等于 K $K$，问在满足上述条件下最少能将序列分成多少段。

数据范围

n$n$<= 5∗105 $5*10^5$， K $K$<=n∗(n−1)2$n*(n-1)over 2$, 1 $1$<=Ai$A_i$<= n <script type="math/tex" id="MathJax-Element-138">n</script>

题解

相信读者们看完题目这题都切了吧。
这题显然是贪心。
线性扫一遍序列，如果可以延长序列的长度就延长，否则就新分一段序列。
同时开个桶维护一下某种元素出现的个数即可。

Code(Pascal)

varzd:array[0..540000] of int64;ql:array[0..540000] of int64;a:array[0..540000] of int64;n,ans,i:longint;k,u:int64;
beginreadln(n,k);ans:=1;for i:=1 to n dobeginread(a[i]);if ql[a[i]]<>ans thenbeginql[a[i]]:=ans;zd[a[i]]:=0;end;u:=u+zd[a[i]];if u>k thenbegininc(ans);zd[a[i]]:=0;ql[a[i]]:=ans;u:=0;end;inc(zd[a[i]]);end;writeln(ans);
end.