cf1208B B. Uniqueness

2943 단어 codeforces
B. Uniqueness time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output You are given an array a1,a2,…,an. You can remove at most one subsegment from it. The remaining elements should be pairwise distinct.
In other words, at most one time you can choose two integers l and r (1≤l≤r≤n) and delete integers al,al+1,…,ar from the array. Remaining elements should be pairwise distinct.
Find the minimum size of the subsegment you need to remove to make all remaining elements distinct.
Input The first line of the input contains a single integer n (1≤n≤2000) — the number of elements in the given array.
The next line contains n spaced integers a1,a2,…,an (1≤ai≤109) — the elements of the array.
Output Print a single integer — the minimum size of the subsegment you need to remove to make all elements of the array pairwise distinct. If no subsegment needs to be removed, print 0.
Examples input 3 1 2 3 output 0 input 4 1 1 2 2 output 2 input 5 1 4 1 4 9 output 2 Note In the first example all the elements are already distinct, therefore no subsegment needs to be removed.
In the second example you can remove the subsegment from index 2 to 3.
In the third example you can remove the subsegments from index 1 to 2, or from index 2 to 3, or from index 3 to 4. 제목: n개의 숫자를 제시하고 가장 작은 한 끝의 연속 구간을 찾아 삭제 작업을 하여 나머지 원소가 중복 원소를 포함하지 않도록 하고 삭제할 최소 구간의 길이를 구한다.사고방식: 역방향으로 문제를 고려하여 삭제할 최소 구간의 길이가 대응하는 최대 몇 개의 수를 보존할 수 있는지, 그리고 구간이 연속되면 왼쪽 구간, 또는 중간 구간, 또는 오른쪽 구간만 삭제할 수 있기 때문이다.두 개의 맵을 이용하여 첫 번째는 왼쪽에서 오른쪽으로 보존할 수 있는 모든 요소의 하표를 저장하고 한 수로 최종 하표를 기록한다.두 번째 맵은 오른쪽에서 왼쪽으로 스캔하여 현재 원소의 오른쪽 부분에 얼마나 많은 수를 보존할 수 있는지 기록하는 데 사용한다. 만약에 오른쪽 부분의 중복 원소가 나타나면 그 중간에 삭제할 원소의 개수를 계산하고 답안을 업데이트할지 판단한다. 그렇지 않으면 표시한다. 만약에 현재 오른쪽 부분의 원소와 처음에 왼쪽 부분의 원소가 나타나면 왼쪽 부분의 원소 삭제 조작을 모의하고 삭제 원소의 개수를 업데이트하여 최상의 답안을 찾아낸다.구체적인 상황은 코드와 주석을 보아라.
#include 
using namespace std;
map book1, book2;
int main() {
	int n;
	int a[2005];
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
	}
	int ans = 99999;
	// p              (   ), q             ,q-p            
	int p = 1, q = n; 
	//       ,             ,            
	while (p <= n) {
		if (book1[a[p]]) {
			break;
		} else {
			book1[a[p]] = p;
		}
		p++;
	}
	//              ,  p                   (  ) 
	p--;
	ans = n - p; //                             
	//        
	while (q >= 1) {
		if (book2[a[q]]) { //   q                , q           ,           
			if (ans > q - p) ans = q - p; //                 ,      
			break;
		} else { //              
			book2[a[q]] = 1;
		}
		if (book1[a[q]] && p >= book1[a[q]]) { //                              ,
		//             ,                           
			if (ans > q - p) ans = q - p;
			p = book1[a[q]] - 1;
		}
		q--;
	} 
	printf("%d
", ans); return 0; }

좋은 웹페이지 즐겨찾기