【JZOJ4911】人生的叹息

Description

给出一个序列，把它划分为尽量少的片段，使每个区间 [l,r] ， s(l,r) 的值 ≤k

其中：

s(l,r)=∑i=lr−1∑j=i+1r[a[i]==a[j]] 其中最外面的[]表示，若里面的布尔表达式为真，则值为1，否则值为0。实际上区间内就是相等的数的对数。

做不出来就是人生的叹息了。

Solution

贪心的尽量给每段划分最长即可。

注意数据规模。

Code

#include<cstdio> #include<cstdlib> #include<algorithm> #define fo(i,j,k) for(int i=j;i<=k;i++) #define fd(i,j,k) for(int i=j;i>=k;i--) #define ll long long #define N 500010 using namespace std; ll now[N]; ll a[N]; int main() { freopen("sigh1.in","r",stdin); freopen("sigh.out","w",stdout); int n; ll k; scanf("%d %lld",&n,&k); fo(i,1,n) scanf("%lld",&a[i]); ll s=0,st=1; ll ans=0; now[a[1]]=1; fo(i,2,n) if(s+now[a[i]]>k) { fo(j,st,i-1) now[a[j]]=0; st=i; now[a[i]]=1; ans++; s=0; } else { s+=now[a[i]]; now[a[i]]++; } printf("%lld",ans+1); }