【思维+树状数组】ZOJ-4117 BaoBao Loves Reading
题目链接:
参考博客:
【题意】:
如果你学过操作系统,其实你就知道这个就是经典的调度算法的FIFO,先进先出算法。
如果你没有学过操作系统,这个就是说有N本书在书架,然后书桌只能容纳K本书,然后先进先出,请问当K取值为[1,n]时,每次拿书的次数为多少。
【题解】:
参考博客小喵的做法,其实只要知道结论真的很简单。
用树状数组维护一个东西,就是相同数字之间的距离,这个距离中有多少个数字是不同的,用Sum数组为存放。
树状数组维护:区间中种类的个数。
Sum[i]:K=i时,不操作的次数。
Ans = n - Sum[i]
然后这个K=i时,会为[i+1,n]作贡献
#include<cstdio> #include<cstring> using namespace std; const int N = 1e5+100; int c[N],a[N],sum[N],pre[N]; int lowbit(int x){ return x&-x; } void update(int x,int val){ while( x < N ){ c[x] += val; x += lowbit(x); } } int getSum(int x){ int Res = 0 ; while ( x > 0 ){ Res += c[x]; x -= lowbit(x); } return Res; } void Init(){ memset(c,0,sizeof(c)); memset(sum,0,sizeof(sum)); memset(pre,0,sizeof(pre)); } int main() { int n,T; scanf("%d",&T); while(T--){ Init(); scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); if( pre[a[i]] ) { update( i , 1 ); update( pre[a[i]], -1); int L = getSum(i) - getSum(pre[a[i]]-1); sum[L] ++ ; pre[a[i]] = i; }else{ update(i,1); pre[a[i]] = i; } } for(int i=1;i<=n;i++){ sum[i] = sum[i-1] + sum[i]; } for(int i=1;i<=n;i++){ printf("%d%c",n-sum[i],i==n? : ); } } return 0; }