P141SUMB spoj PTIT – ROUND 1B – Hoán vị

Nguồn đề bài: http://www.spoj.com/PTIT/problems/P141SUMB/

1. Đề bài P141SUMB spoj

Một hoán vị là một dãy số có n phần tử mà các số từ 1 đến n xuất hiện 1 lần duy nhất.

Giờ đây, bạn được cho một dãy gồm n số nguyên, mỗi số không nhỏ hơn 1 và không lớn hơn 5000.

Bạn được phép thay 1 số bằng 1 con số khác tùy ý sao cho số phép biến đổi là ít nhất để dãy số đã cho trở thành 1 hoán vị.

Input

Dòng đầu tiên chứa số nguyên n ( 1 <= n <= 5000), số phần tử của dãy số.

Dòng thứ 2 chứa n số nguyên a[i] (1 <= a[i] <= 5000,  1<= i <= n).

Output

Dòng duy nhất là số phép biến đổi ít nhất.

Example

Test 1:

Input:

3

3 1 2

Output:

0

Test 2:

Input:

2

2 2

Output:

1

Test 3:

Input:

5

5 3 3 3 1

Output:

2

2. Cách làm P141SUMB spoj PTIT

sử dụng kỹ thuật DD (đánh dấu)…

– Xây dựng mảng A, với A[i] cho biết số i có xuất hiện không.

– Sau khi xây dựng mảng A, thực hiện đếm các A[i]=false. và đó chính là kết quả bài toán.

Nếu các bạn không hiểu, có thể comment để mình trả lời