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

Chúng tôi nhận thiết kế web công ty, thiết kế web thương mại điện tử, shop, thiết kế web blog cá nhân, viết phần mềm PC.

Liên hệ ngay: 035.870.8844 - Giá chỉ từ 2-3 triệu.

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 🙂

3. Code tham khảo P141SUMB spoj PTIT

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *