Problem: USACO.
Internal solution: Solution - Out of Place (USACO Bronze 2018 January)
I think the internal solution of that problem is wrong (or I have some confusion).
Consider the test:
5
2 3 1 5 4
The solution for that (according to the sample code) is 4.
But consider this swaps:
2 3 1 5 4 → 1 3 2 5 4 → 1 2 3 5 4 → 1 2 3 4 5.
We can see it took only 3 swaps.
This is my code (output 3 swaps in that case):
#include <bits/stdc++.h>
using namespace std;
const string FNAME = "outofplace";
int arr[100], sorted[100];
int main() {
freopen((FNAME + ".in").c_str(), "r", stdin);
freopen((FNAME + ".out").c_str(), "w", stdout);
int n; cin >> n;
for (int i = 0; i < n; ++i) {
cin >> arr[i];
sorted[i] = arr[i];
}
sort(sorted, sorted + n);
int res = 0;
for (int i = 0; i < n; ++i) {
if (arr[i] == sorted[i]) continue;
for (int j = i + 1; j < n; ++j) {
if (sorted[i] == arr[j]) {
// cout << "swap " << i << " " << j << endl;
swap(arr[i], arr[j]);
++res;
break;
}
}
}
cout << res;
return 0;
}
This is the judge of my code:
Thanks for reading. (sorry for my bad English)