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
const fi='';
nmax=5000;
type data=word;
var
f:text;
A:array[1..5000] of boolean;
n:data;
procedure xuli;
var i:data;
tmp:data;
dem:real;
begin
fillchar(a,sizeof(a),false);
assign(f,fi); reset(f);
readln(f,n);
for i:=1 to n do
begin
read(f,tmp);
a[tmp]:=true;
end;
close(f);
dem:=0;
for i:=1 to n do
if a[i]=false THEN
dem:=dem+1;
writeln(round(dem));
end;
begin
xuli;
end.
