cf1208B B. Uniqueness
2943 단어 codeforces
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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Codeforces Round #715 Div. 2C The Sports Festival: 구간 DP전형구간 DP의 초전형. 이하, 0-indexed. 입력을 정렬하여 어디서나 시작하고 최적으로 좌우로 계속 유지하면 좋다는 것을 알 수 있습니다. {2000})$의 주문이 된다. 우선, 입력을 소트하여 n개의 요소를 $...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.