锐客网

  1. 首页 > it技术 > >

BSOJ 4208 -- 【USACO 2013 Jan】奶牛队列

【BSOJ 4208 -- 【USACO 2013 Jan】奶牛队列】Description
FJ的奶牛（1≤n≤100000）排成一排。每头奶牛由一个整数”品种ID（0……1000000000之间）”表示其类别；多个奶牛的品种ID可以是一样的.FJ想让他的牛看起来更令人印象深刻，需要将一部份品种移出队列，以便同一类奶牛站在一起的宽度最长，也就是一个大的连续的块的奶牛都有相同的ID。F选择最多K个品种从队列中移出，请你回答最后该最大连续块的奶牛数量是多少？
Input
* 1行：两个用空格隔开的整数：N和K。
* 2..1+N行: 依次表示第I个奶牛的品种ID.
Output
* 1行：最大连续块的奶牛数量
Sample Input
9 1
2
7
3
7
7
3
7
5
7
Sample Output
4
Hint
样例说明：
队列有9头奶牛，以品种编号为2，7，3，7，7，3，7，5，7。FJ想去除最多1个品种奶牛。最后选择品种3移出，则连续有4个品种为7的奶牛站在一起。
化动为静，
每次只算区间右端的数的最大数量。
转化成O（n）
综合为O（nlogn）

#include #include #include #include #include #include using namespace std; mapMap,M; int t=0; int A[100005]; int n,k; int last[100005]; int ha[100005]; int cnt=0; void Add(int x){ ha[M[x]]++; if(ha[M[x]]==1)cnt++; } void Del(int x){ ha[M[x]]--; if(ha[M[x]]==0)cnt--; } int main(){ scanf("%d%d",&n,&k); for(int i=1; i<=n; i++){ scanf("%d",&A[i]); if(M[A[i]]==0)M[A[i]]=++t; last[i]=Map[A[i]]; Map[A[i]]=i; } int l=1; int Ans=0; for(int i=1; i<=n; i++){ Add(A[i]); while(cnt-1>k){ Del(A[l]); l++; } Ans=max(Ans,ha[M[A[i]]]); } cout

    推荐阅读


    上一篇：BLE|BLE 包结构及传输速率

    下一篇：工具使用|Source Insight 常用设置和快捷键大全