zoj 3790 Consecutive Blocks(鏈表重點是思想)

There are N (1 ≤ N ≤ 10⁵) colored blocks (numbered 1 to N from left to right) which are lined up in a row. And the i-th block's color is C_i (1 ≤ C_i ≤ 10⁹). Now you can remove at most K (0 ≤ K ≤ N) blocks, then rearrange the blocks by their index from left to right. Please figure out the length of the largest consecutive blocks with the same color in the new blocks created by doing this.

For example, one sequence is {1 1 1 2 2 3 2 2} and K=1. We can remove the 6-th block, then we will get sequence {1 1 1 2 2 2 2}. The length of the largest consecutive blocks with the same color is 4.

Input

Input will consist of multiple test cases and each case will consist of two lines. For each test case the program has to read the integers N and K, separated by a blank, from the first line. The color of the blocks will be given in the second line of the test case, separated by a blank. The i-th integer means C_i.

Output

Please output the corresponding length of the largest consecutive blocks, one line for one case.

Sample Input

8 1
1 1 1 2 2 3 2 2

Sample Output

4

Source: ZOJ Monthly, June 2014

題意：

給你一個長度為N (1 ≤ N ≤ 10⁵) 的序列。序列中值的范圍為C_i (1 ≤ C_i ≤ 10⁹).你可以從序列中取出至多k個。但相對位置不能動。現在問你通過取出操作能夠得到數字一樣的序列的最長長度。

思路：

思路是非常簡單的。比賽時很快就相出了做法。但到最後都沒做出來。就因為寫錯了一個變量。僅以此文紀念自己的逗比。改掉自己馬虎的毛病。話歸正傳。既然我們要求的是數字一樣的序列的最長長度。那麼對於序列中的每一個值都有在最長序列中的可能性。所以我們只需要考慮包含了序列第i個值。且用到前面的i的值的一些的最長長度。現在關鍵是這個k怎麼刪呢。當前值設為v。如果我們知道上個出現v的位置和上個v用到了前面的那些v和上個位置的最大長度。為了使連續v最長肯定就要想辦法是當前v和上個v連在一起。如果他們直接相鄰的話肯定他的最長長度為上個位置最長長度加1.否則肯定要用除去中間的其他值使得序列連續。那麼肯定要去掉當前位置-上個位置+1個元素。所以思路就清晰了。對於每個值維護一個鏈表。表示它用到了前面的那些v還有多少個k可以刪。然後把這n個序列依次往自己對應的鏈表裡加。如果k夠的話就直接加。不夠的話就把鏈表從後往前刪然後恢復k。為什麼刪後面的呢。因為從當前位置要連續。不刪前面刪哪裡啊。由於c比較大所以要hash一下。由於每個元素至多被加進和移除鏈表依次。所以最多2*n次操作。這樣就華麗的以O(n)的時間復雜度解決了這道題。

詳細見代碼：

#include
#include
#include
#include
using namespace std;
const int maxn=100010;
int H[maxn],arr[maxn],n,m,ptr;
void init()//hash初始化
{
    ptr=0;
    sort(H,H+m);
    m=unique(H,H+m)-H;
}
struct node//鏈表頭結點
{
    int k,st,tail,len;//k還有k個元素可以刪。st最後一個加入元素的指針。tail鏈表尾。方便從後往前刪。len鏈表長度
} hd[maxn];
struct nd
{
    int id,next;//鏈表結點。id為在序列中的下標。
} me[maxn];
int Hash(int x)
{
    return lower_bound(H,H+m,x)-H;
}
int main()
{
    int i,k,v,tl,p,ans;
    while(~scanf("%d%d",&n,&k))
    {
        ans=1;
        for(i=0;i