#include <cstdio>
#include <cstring>

#define MAX_SIZE 1000001
#define PRIME 99991

struct Node {
	int id;
	int ideaId;
	int index;
	Node *next;
};

struct Item {
	int id;
	int index;

	friend static bool operator < (const Item &a, const Item &b) {
		return (a.index < b.index);
	}

	friend static void swap(Item &a, Item &b) {
		Item tmp;
		tmp.id = a.id;
		tmp.index = a.index;
		a.id = b.id;
		a.index = b.index;
		b.id = tmp.id;
		b.index = tmp.index;
	}
};

Node *ids[MAX_SIZE];
Node nodes[MAX_SIZE];
int nodeSize;
Node *hashes[PRIME];
int size;

class Heap {
public:
	Heap() {
		_size = 0;
	}

	void init() {
		_size = 0;
	}

	void push(Item &item) {
		_vals[_size].id = item.id;
		_vals[_size++].index = item.index;	
		checkHeapPropertyUp(_size-1);
	}

	void push(int id, int index) {
		_vals[_size].id = id;
		_vals[_size++].index = index;	
		checkHeapPropertyUp(_size-1);
	}

	void pop() {
		if (!empty()) {
			_vals[0] = _vals[--_size];
			if (!empty()) {
				checkHeapProperty(0);
			}
		}
	}

	Item top() {
		return (_vals[0]);
	}

	bool empty() {
		return (0 == _size);
	}



private:
	void checkHeapProperty(int index) {
		int left = (index << 1) + 1;
		int right = left + 1;
		if (right < _size && _vals[right] < _vals[index] && _vals[right] < _vals[left]) {
			swap(_vals[right], _vals[index]);
			checkHeapProperty(right);
		} else if (left < _size && _vals[left] < _vals[index]) {
			swap(_vals[left], _vals[index]);
			checkHeapProperty(left);
		}
	}

	void checkHeapPropertyUp(int index) {
		if (0 == index) {
			return;
		}
		int parent = (index-1) >> 1;
		if (_vals[index] < _vals[parent]) {
			swap(_vals[index], _vals[parent]);
			checkHeapPropertyUp(parent);
		}
	}

	int _size;
	Item _vals[MAX_SIZE];
};

Heap heap;

void init()
{
	memset(nodes, 0, sizeof(nodes));
	nodeSize = 0;
	memset(hashes, 0, sizeof(hashes));
	heap.init();
}

Node* getHash(int ideaId)
{
	int index = ideaId % PRIME;
	for (Node *p = hashes[index]; p; p = p->next) {
		if (p->ideaId == ideaId) {
			return (p);
		}
	}
	nodes[nodeSize].id = nodeSize;
	nodes[nodeSize].index = -1;
	nodes[nodeSize].ideaId = ideaId;
	nodes[nodeSize].next = hashes[index];
	hashes[index] = &nodes[nodeSize++];
	return (hashes[index]);
}



int main()
{
	int ideaId, id;

	scanf("%d", &size);
	init();
	for (int i = 0; i < size; ++i) {
		scanf("%d", &ideaId);
		ids[i] = getHash(ideaId);
	}
	int idSize = nodeSize;
	int idCnt = 0;
	int ret = MAX_SIZE;
	for (int i = 0; i < size; ++i) {
		heap.push(ids[i]->id, i);
		if (-1 == ids[i]->index) {
			idCnt ++;
		}
		ids[i]->index = i;
		if (idSize == idCnt) {
			while (ids[heap.top().index]->index != heap.top().index) {
				heap.pop();
			}
			if (i - heap.top().index + 1 < ret) {
				ret = i - heap.top().index + 1;
			}
		}
	}
	printf("%d\n", ret);
	return (0);
}

• Re:我能告诉你我只要30+行代码吗： (647) FreagleX 2014-08-02 20:46:34
  • Re:我能告诉你我只要30+行代码吗： (20) Dandi 2014-09-03 11:11:23