2354번 - 비교교환 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 44 | 20 | 13 | 43.333% |
문제
n개의 수 A[1], A[2], …, A[n]이 있을 때, 1 ≤ a < b ≤ n인 두 정수 a, b에 대해서 비교교환(Compare-Exchange) 함수는 다음과 같이 정의된다.
CE(a, b)
if(A[a] > A[b])
Swap(A[a], A[b]);
즉, 두 값을 비교하여 더 작은 값이 앞으로 오도록 하는 함수이다. 이와 같은 CE함수를 나열해 놓은 것을 CE프로그램이라 한다. 어떤 CE프로그램을 수행한 후, 어떤 A[1], A[2], …, A[n]에 대해서도 A[1]에 최솟값(A[1], A[2], …, A[n] 중에서)이 저장될 경우, 그 CE프로그램을 최소-탐색-CE프로그램 이라고 한다. 특히 이와 같은 최소-탐색-CE프로그램들 중에서 프로그램 내의 CE함수 호출을 임의로 하나 제거해도 최소-탐색-CE프로그램인 것을 안정적인-최소-탐색-CE프로그램 이라고 한다.
어떤 CE프로그램이 주어졌을 때, 여기에 프로그램의 마지막 부분에 CE함수 호출을 최소로 추가하여 안정적인-최소-탐색-CE프로그램이 되도록 하려 한다.
입력
첫째 줄에 두 정수 n(2 ≤ n ≤ 10,000), m(0 ≤ m ≤ 25,000)이 주어진다. m은 주어진 CE프로그램의 CE함수 호출 횟수이다. 다음 줄에는 2m개의 정수가 주어진다. 2개씩 순서대로 CE함수 호출에서의 두 인자 a, b이다.
출력
첫째 줄에 추가할 CE함수 호출 횟수의 최솟값을 출력한다.
예제 입력 1
3 3 1 2 2 3 1 2
예제 출력 1
2
출처
ICPC > Regionals > Europe > Central European Regional Contest > CERC 2001 E번
- 빠진 조건을 찾은 사람: portableangel
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호