Skip to content

11558: 【原1558】最长序列问题

题目

题目描述

author: Zhiyin Chen 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1558

Description

农场主有N头奶牛 (1 <= N <= 100,000) 排成一行. 每头牛都有一个种类标签B(i),标签为0~1,000,000,000的数字。存在多头牛用相同标签的情况。农场主想选择K种标签,使得移去选择标签对应的牛后,奶牛序列中,标签相同且相邻的最大连续子序列的长度最长。

Input Format

一行,两个空格隔开的整数N,K。i+1行,B(i)

Output Format

移去选择标签对应的牛后,标签相同且相邻的最大连续子序列的长度。

Sample Input

9 1
2
7
3
7
7
3
7
5
7

Sample Output

4

Neight99's solution

#include <iostream>

using namespace std;

const int hashNum = 1e4 + 9;
const int maxN = 1e5 + 10;

int calHash(int x) { return x % hashNum; }

class Hash {
   private:
    struct Node {
        int data;
        int count;
        Node *next;

        Node(int d = 0, int c = 1, Node *ne = 0)
            : data(d), count(c), next(ne) {}
    };
    Node *data[hashNum];

   public:
    Hash() {
        for (int i = 0; i < hashNum; i++) {
            data[i] = 0;
        }
    }

    ~Hash() {
        for (int i = 0; i < hashNum; i++) {
            if (!data[i]) {
                Node *p = data[i], *q;
                while (p != NULL) {
                    q = p->next;
                    delete p;
                    p = q;
                }
            }
        }
    }

    int insert(int x) {
        int index = calHash(x);
        if (!data[index]) {
            data[index] = new Node(x);
            return 1;
        } else {
            Node *p = data[index];
            while (p != NULL && p->data != x) {
                p = p->next;
            }
            if (p != NULL) {
                p->count++;
                return p->count;
            } else {
                p = new Node(x);
                p->next = data[index];
                data[index] = p;
                return 1;
            }
        }
    }

    int remove(int x) {
        int index = calHash(x);
        if (!data[index]) {
            return 0;
        } else {
            Node *p = data[index];
            while (p != NULL && p->data != x) {
                p = p->next;
            }
            if (p != NULL) {
                p->count--;
                return (p->count);
            } else {
                return 0;
            }
        }
    }
};

int input[maxN];
Hash hashLabel;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N, K, ans = 0, count = 0, start = 0;
    cin >> N >> K;

    for (int i = 0; i < N; i++) {
        cin >> input[i];
        int temp = hashLabel.insert(input[i]);

        ans = (ans < temp) ? temp : ans;

        if (temp == 1) {
            count++;
        }

        if (count > K + 1) {
            int i;
            for (i = start;; i++) {
                if (hashLabel.remove(input[i]) == 0) {
                    break;
                }
            }
            start = i + 1;
            count--;
        }
    }

    cout << ans << '\n';

    return 0;
}