Link Sub: http://www.spoj.com/PTIT/problems/P166SUMA/
Người Gửi: Dương Lee
- Problem:
Captain Boomerang là người có khả năng rất đặc biệt. Như biệt danh của mình, anh là master trong việc sử dụng những chiếc boomerang. Ngoài ra, Captain Boomerang còn có sở thích rất kỳ lạ đó là thích chơi với các dãy hoán vị. Trong lúc rảnh rỗi, anh có nghĩ ra bài toán này và đem đi đố mọi người trong team.
Cho 1 dãy gồm n phần tử: a1, a2, …, an (1 <= ai <= 5000). Nhiệm vụ là phải chuyển dãy trên về 1 dãy hoán vị n phần tử, biết trong 1 bước, chỉ được thay đổi giá trị của 1 phần tử. Hỏi xem cần tối thiếu bao nhiêu bước để hoàn thành nhiệm vụ.
Biết rằng 1 dãy hoán vị n phần tử là hoán vị bất kỳ của dãy số 1, 2, 3, …, n
Do không ai trong team có sở thích kỳ lạ này nên cũng chẳng ai muốn làm, các bạn hãy giải đáp bài toán này của Captain Boomerang nhé.
Cho 1 dãy gồm n phần tử: a1, a2, …, an (1 <= ai <= 5000). Nhiệm vụ là phải chuyển dãy trên về 1 dãy hoán vị n phần tử, biết trong 1 bước, chỉ được thay đổi giá trị của 1 phần tử. Hỏi xem cần tối thiếu bao nhiêu bước để hoàn thành nhiệm vụ.
Biết rằng 1 dãy hoán vị n phần tử là hoán vị bất kỳ của dãy số 1, 2, 3, …, n
Do không ai trong team có sở thích kỳ lạ này nên cũng chẳng ai muốn làm, các bạn hãy giải đáp bài toán này của Captain Boomerang nhé.
Dòng đầu tiên nhập 1 nguyên số n (1 <= n <= 5000).
Dòng tiếp theo nhập dãy gồm n số a1, a2, …, an (1 <= ai <= 5000).
Output
Example:
In ra kết quả bài toán – số bước ít nhất cần thực hiện.
Input
5
4 5 4 4 1
Output:
2
Input
2
1 1
Output:
1
- Solution:
Input
2
1 1
Output:
1
Số các số còn thiếu = số bước cần thay đổi.
Sử dụng mảng đánh dấu để đếm các số còn thiếu
Sử dụng mảng đánh dấu để đếm các số còn thiếu
- Code:
C++:
https://ideone.com/2Osuid
#include <iostream>
using namespace std;
int main ()
{
int n;
cin>>n;
int arr[5003] = {0};
int a;
for (int i=0; i<n; i++)
{
cin>>a;
arr[a] = 1;
}
int count = 0;
for (int i=1; i<=n; i++)
if (arr[i]==0)
count++;
cout<<count;
return 0;
}JAVA:
...Python:
...